Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
From MaRDI portal
Publication:4984870
DOI10.1145/3368630OpenAlexW2994887275WikidataQ126593767 ScholiaQ126593767MaRDI QIDQ4984870
Wojciech Nadara, Roman Rabinovich, Felix Reidl, Sebastian Siebertz, Marcin Pilipczuk
Publication date: 21 April 2021
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8949/
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XXII. Irrelevant vertices in linkage problems
- 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
- Characterising bounded expansion by neighbourhood complexity
- Treedepth bounds in linear colorings
- Reconfiguration on nowhere dense graph classes
- What's in a crowd? Analysis of face-to-face behavioral networks
- Reconfiguration on sparse graphs
- Orderings on graphs and game coloring number
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Connected components in random graphs with given expected degree sequences
- Constant-factor approximation of the domination number in sparse graphs
- Approximation algorithms via contraction decomposition
- Polynomial bounds for centered colorings on proper minor-closed graph classes
- Structural sparsity of complex networks: bounded expansion in random models and real-world 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
- Tree-depth, subgraph coloring and homomorphism bounds
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- From the Cover: The structure of scientific collaboration networks
- Colouring and Covering Nowhere Dense Graphs
- Domination Problems in Nowhere-Dense Classes
- Enumeration of monadic second-order queries on trees
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- Polynomial-time data reduction for dominating set
- Stable graphs
- 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
- Positive-Instance Driven Dynamic Programming for Treewidth.
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
- On the number of types in sparse graphs
- Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Collective dynamics of ‘small-world’ networks
- On distance ‐dominating and ‐independent sets in sparse graphs
- Testing first-order properties for subclasses of sparse graphs
- The price of anarchy in network creation games
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- Machine Learning: ECML 2004
- The average distances in random graphs with given expected degrees
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On the generalised colouring numbers of graphs that exclude a fixed minor
This page was built for publication: Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
