Vis enkel innførsel

dc.contributor.authorTelle, Jan Arne
dc.contributor.authorJaffke, Lars
dc.contributor.authorStrømme, Torstein Jarl Fagerbakke
dc.contributor.authorKwon, O-Joung
dc.PublishedTelle JA, Jaffke L, Strømme TFJ, Kwon O. Mim-Width III. Graph powers and generalized distance domination problems. Theoretical Computer Science. 2019;796:216-236eng
dc.description.abstractWe generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance-r Dominating Set and Distance-r Independent Set. We show that these distance problems are in XP parameterized by the structural parameter mim-width, and hence polynomial-time solvable on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. We obtain these results by showing that taking any power of a graph never increases its mim-width by more than a factor of two. To supplement these findings, we show that many classes of (σ,ρ) problems are W[1]-hard parameterized by mimwidth + solution size. We show that powers of graphs of tree-width w − 1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1.en_US
dc.rightsAttribution CC BYeng
dc.titleMim-Width III. Graph powers and generalized distance domination problemsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright 2019 The Authorsen_US
dc.source.journalTheoretical Computer Science

Tilhørende fil(er)


Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY