Domination Problems in Nowhere-Dense Classes of Graphs - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




Domination Problems in Nowhere-Dense Classes of Graphs - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We investigate the parameterized complexity of generalisations and variationsof the dominating set problem on classes of graphs that are nowhere dense. Inparticular, we show that the distance-d dominating-set problem, also known asthe k,d-centres problem, is fixed-parameter tractable on any class that isnowhere dense and closed under induced subgraphs. This generalises knownresults about the dominating set problem on H-minor free classes, classes withlocally excluded minors and classes of graphs of bounded expansion. A keyfeature of our proof is that it is based simply on the fact that these graphclasses are uniformly quasi-wide, and does not rely on a structuraldecomposition. Our result also establishes that the distance-d dominating-setproblem is FPT on classes of bounded expansion, answering a question of Ne{\vs}et{\v{r}}il and Ossona de Mendez.



Autor: Anuj Dawar, Stephan Kreutzer

Fuente: https://arxiv.org/







Documentos relacionados