Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

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

zbMATH Keywords

sparse graph classesgeneralized coloring numbersuniform quasi-widenessempirical evaluation of algorithms

Mathematics Subject Classification ID

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

• GraphBase
• Pajek
• Pajek datasets
• SNAP
• ComputeTW
• KONECT
• GitHub

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