License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.14
URN: urn:nbn:de:0030-drops-89493
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8949/
Go to the corresponding LIPIcs Volume Portal

Nadara, Wojciech ; Pilipczuk, Marcin ; Rabinovich, Roman ; Reidl, Felix ; Siebertz, Sebastian

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

pdf-format:
LIPIcs-SEA-2018-14.pdf (1 MB)

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 paper we study two structural properties of these graph classes that are of particular importance in this context, namely 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.

BibTeX - Entry

@InProceedings{nadara_et_al:LIPIcs:2018:8949,
  author =	{Wojciech Nadara and Marcin Pilipczuk and Roman Rabinovich and Felix Reidl and Sebastian Siebertz},
  title =	{{Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8949},
  URN =		{urn:nbn:de:0030-drops-89493},
  doi =		{10.4230/LIPIcs.SEA.2018.14},
  annote =	{Keywords: Empirical Evaluation of Algorithms, Sparse Graph Classes, Generalized Coloring Numbers, Uniform Quasi-Wideness}
}

Keywords: Empirical Evaluation of Algorithms, Sparse Graph Classes, Generalized Coloring Numbers, Uniform Quasi-Wideness
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI