Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
Open Access
- 10 December 2019
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 24 (2) , 1-34
Abstract
The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. In this article, we study two structural properties of these graph classes that are of particular importance in this context: the property of having bounded generalized coloring numbers and the property of being uniformly quasi-wide . We provide experimental evaluations of several algorithms that approximate these parameters on real-world graphs. On the theoretical side, we provide a new algorithm for uniform quasi-wideness with polynomial size guarantees in graph classes of bounded expansion and show a lower bound indicating that the guarantees of this algorithm are close to optimal in graph classes with fixed excluded minor.Keywords
All Related Versions
Funding Information
- Marie Skłodowska-Curie (665778)
- European Research Council
- ERC Consolidator Grant DISTRUCT (648527)
- Recent trends in kernelization: theory and experimental evaluation
- European Union's Horizon 2020 research and innovation programme
- National Science Centre of Poland via POLONEZ grant (UMO-2015/19/P/ST6/03998)
- Homing programme of the Foundation for Polish Science
- European Union under the European Regional Development Fund
This publication has 52 references indexed in Scilit:
- Constant-factor approximation of the domination number in sparse graphsEuropean Journal of Combinatorics, 2013
- High-Resolution Measurements of Face-to-Face Contact Patterns in a Primary SchoolPLOS ONE, 2011
- Approximation algorithms via contraction decompositionCombinatorica, 2010
- Grad and classes with bounded expansion III. Restricted graph homomorphism dualitiesEuropean Journal of Combinatorics, 2008
- Grad and classes with bounded expansion II. Algorithmic aspectsEuropean Journal of Combinatorics, 2008
- Grad and classes with bounded expansion I. DecompositionsEuropean Journal of Combinatorics, 2008
- The Bidimensionality Theory and Its Algorithmic ApplicationsThe Computer Journal, 2007
- The human disease networkProceedings of the National Academy of Sciences, 2007
- Mapping the Gnutella networkIEEE Internet Computing, 2002
- The structure of the nervous system of the nematode Caenorhabditis elegansPhilosophical Transactions of the Royal Society of London. B, Biological Sciences, 1986