Constant-factor approximation of the domination number in sparse graphs
From MaRDI portal
Publication:1943391
DOI10.1016/j.ejc.2012.12.004zbMath1260.05111arXiv1110.5190OpenAlexW2143305437MaRDI QIDQ1943391
Publication date: 19 March 2013
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.5190
linear-time constant-factor algorithmproper classes closed on topological minorsproper minor-closed graph classes
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)
Related Items (25)
Improved bounds for weak coloring numbers ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Harmless sets in sparse classes ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ On coloring numbers of graph powers ⋮ Towards a characterization of universal categories ⋮ On weighted sublinear separators ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Edge degeneracy: algorithmic and structural results ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Bounding generalized coloring numbers of planar graphs using coin models ⋮ Unnamed Item ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Uniform orderings for generalized coloring numbers ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Unnamed Item ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ VC-dimension and Erdős-Pósa property ⋮ Packing and covering balls in graphs excluding a minor ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Twin-width and generalized coloring numbers ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Digraphs of Bounded Width ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
This page was built for publication: Constant-factor approximation of the domination number in sparse graphs
