Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 권오정 | - |
dc.date.accessioned | 2022-11-18T04:55:11Z | - |
dc.date.available | 2022-11-18T04:55:11Z | - |
dc.date.issued | 2019-12 | - |
dc.identifier.citation | THEORETICAL COMPUTER SCIENCE, v. 796, page. 216-236 | en_US |
dc.identifier.issn | 0304-3975; 1879-2294 | en_US |
dc.identifier.uri | https://www.sciencedirect.com/science/article/pii/S0304397519305560?via%3Dihub | en_US |
dc.identifier.uri | https://repository.hanyang.ac.kr/handle/20.500.11754/177000 | - |
dc.description.abstract | We 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 -hard parameterized by mim-width + solution size. We show that powers of graphs of tree-width 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.description.sponsorship | Supported by the Bergen Research Foundation (BFS). Supported by Institute for Basic Science, South Korea (IBS-R029-C1), and the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294), and the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (ERC consolidator grant DISTRUCT, agreement No. 648527). Part of the research took place while Kwon was at Logic and Semantics, Technische Universitat Berlin, Berlin, Germany. | en_US |
dc.language | en | en_US |
dc.publisher | ELSEVIER SCIENCE BV | en_US |
dc.subject | Graph width parameters; Graph classes; Distance domination problems; Parameterized complexity; Graph powers; Leaf powers | en_US |
dc.title | Mim-Width III. Graph Powers and Generalized Distance Domination Problems | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1016/j.tcs.2019.09.012 | en_US |
dc.relation.journal | THEORETICAL COMPUTER SCIENCE | - |
dc.contributor.googleauthor | Jaffke, Lars | - |
dc.contributor.googleauthor | Kwon, O-joung | - |
dc.contributor.googleauthor | Stromme, Torstein J. F. | - |
dc.contributor.googleauthor | Telle, Jan Arne | - |
dc.relation.code | 2019002154 | - |
dc.sector.campus | S | - |
dc.sector.daehak | COLLEGE OF NATURAL SCIENCES[S] | - |
dc.sector.department | DEPARTMENT OF MATHEMATICS | - |
dc.identifier.pid | ojoungkwon | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.