Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
From MaRDI portal
Publication:5140724
DOI10.4230/LIPIcs.SEA.2018.14zbMath1493.68398arXiv1802.09801OpenAlexW2963948910MaRDI QIDQ5140724
Felix Reidl, Wojciech Nadara, Roman Rabinovich, Sebastian Siebertz, Marcin Pilipczuk
Publication date: 16 December 2020
Full work available at URL: https://arxiv.org/abs/1802.09801
sparse graph classesgeneralized coloring numbersuniform quasi-widenessempirical evaluation of algorithms
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
On the parameterized complexity of reconfiguration of connected dominating sets ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Sparsity. Graphs, structures, and algorithms
- Treewidth computations. I: Upper bounds
- Homomorphism preservation on quasi-wide classes
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Colouring graphs with bounded generalized colouring number
- Orderings on graphs and game coloring number
- Connected components in random graphs with given expected degree sequences
- Constant-factor approximation of the domination number in sparse graphs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- On nowhere dense graphs
- From the Cover: The structure of scientific collaboration networks
- Domination Problems in Nowhere-Dense Classes
- Polynomial-time data reduction for dominating set
- Community structure in social and biological networks
- Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
- Kernelization and Sparseness: the case of Dominating Set
- The Generalised Colouring Numbers on Classes of Bounded Expansion
- Deciding First-Order Properties of Nowhere Dense Graphs
- The Average Distance in a Random Graph with Given Expected Degrees
- First order properties on nowhere dense structures
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Collective dynamics of ‘small-world’ networks
- Testing first-order properties for subclasses of sparse graphs
- The average distances in random graphs with given expected degrees
- On the generalised colouring numbers of graphs that exclude a fixed minor
