Domination Problems in Nowhere-Dense Classes

DOI10.4230/LIPICS.FSTTCS.2009.2315zbMath1248.68241OpenAlexW2241818993MaRDI QIDQ2920123

Anuj Dawar, Stephan Kreutzer

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_3d5c.html

zbMATH Keywords

dominating set\(H\)-minor free graphsnowhere-dense graph classesdistance-\(d\) dominating setfixed-parameter tractablility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (42)

Enumeration for FO Queries over Nowhere Dense Graphs ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Modeling limits in hereditary classes: reduction and application to trees ⋮ Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Kernelization of edge perfect code and its variants ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ Reconfiguration on nowhere dense graph classes ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ k-Efficient domination: Algorithmic perspective ⋮ On low tree-depth decompositions ⋮ Unnamed Item ⋮ Perfect domination and small cycles ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Interpreting nowhere dense graph classes as a classical notion of model theory ⋮ Unnamed Item ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Confronting intractability via parameters ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ On directed covering and domination problems ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Tight Bounds for Linkages in Planar Graphs ⋮ Reconfiguration on sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Unnamed Item ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Twin-width and polynomial kernels ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Directed Covering and Domination Problems ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

This page was built for publication: Domination Problems in Nowhere-Dense Classes