Domination problems in nowhere-dense classes of graphs

DOI10.4230/LIPICS.FSTTCS.2009.2315zbMATH Open1248.68241OpenAlexW2241818993MaRDI QIDQ2920123FDOQ2920123

Publication date: 24 October 2012

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

Recommendations

Polynomial kernels and wideness properties of nowhere dense graph classes
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Polynomial kernels and wideness properties of nowhere dense graph classes
Directed nowhere dense classes of graphs
FPT algorithms for domination in sparse graphs and beyond

dominating set \(H\)-minor free graphs nowhere-dense graph classes distance-\(d\) dominating set fixed-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)

Cited In (45)

On the parameterized complexity of \([1,j]\)-domination problems
On the parameterized complexity of reconfiguration of connected dominating sets
Structural properties and constant factor-approximation of strong distance-\(r\) dominating sets in sparse directed graphs
Lossy kernels for connected dominating set on sparse graphs
Title not available (Why is that?)
Smaller kernels for several FPT problems based on simple observations
On directed covering and domination problems
Perfect domination and small cycles
Recovering sparse graphs
On directed covering and domination problems
Graph minors and parameterized algorithm design
Reconfiguration on nowhere dense graph classes
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
Polynomial kernels and wideness properties of nowhere dense graph classes
Lossy kernels for connected dominating set on sparse graphs
Enumeration for FO Queries over Nowhere Dense Graphs
Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
Colouring and covering nowhere dense graphs
Computing vertex-surjective homomorphisms to partially reflexive trees
Kernelization of edge perfect code and its variants
Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
Title not available (Why is that?)
Title not available (Why is that?)
Polynomial kernels and wideness properties of nowhere dense graph classes
Confronting intractability via parameters
On low tree-depth decompositions
On the Parameterized Complexity of [1,j]-Domination Problems
FPT algorithms for domination in sparse graphs and beyond
The kernelization complexity of connected domination in graphs with (no) small cycles
Irrelevant vertices for the planar disjoint paths problem
Interpreting nowhere dense graph classes as a classical notion of model theory
Dominating set is fixed parameter tractable in claw-free graphs
Directed nowhere dense classes of graphs
k-Efficient domination: Algorithmic perspective
Modeling limits in hereditary classes: reduction and application to trees
Tight bounds for linkages in planar graphs
Improved kernel results for some FPT problems based on simple observations
Bounds on half graph orders in powers of sparse graphs
Title not available (Why is that?)
Title not available (Why is that?)
Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
Twin-width and polynomial kernels
Reconfiguration on sparse graphs
Coloring and covering nowhere dense graphs

This page was built for publication: Domination problems in nowhere-dense classes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920123)