Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
作者： Felix Reidl , Roman Rabinovich , Marcin Pilipczuk , Sebastian Siebertz , Wojciech Nadara
DOI:
关键词:
摘要: The notions of bounded expansion and nowhere denseness not only offer robust general definitions uniform sparseness graphs, they also describe the tractability boundary for several important algorithmic questions. In this paper we study two structural properties these graph classes that are particular importance in context, namely property having generalized coloring numbers being uniformly quasi-wide. We provide experimental evaluations algorithms approximate parameters on real-world graphs. On theoretical side, a new algorithm quasi-wideness with polynomial size guarantees show lower bound indicating close to optimal fixed excluded minor.
harvard.edu
arxiv.org参考文章(74)
Daniel Lokshtanov, Saket Saurabh, Lukasz Kowalik, Marcin Pilipczuk, Marek Cygan, Fedor V. Fomin, Michal Pilipczuk, Daniel Marx, Parameterized Algorithms ,(2015)
Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz, Distributed Domination on Graph Classes of Bounded Expansion acm symposium on parallel algorithms and architectures. pp. 143- 151 ,(2018) , 10.1145/3210377.3210383
Roman Rabinovich, Michal Pilipczuk, Sebastian Siebertz, Stephan Kreutzer, The Generalised Colouring Numbers on Classes of Bounded Expansion mathematical foundations of computer science. ,vol. 58, pp. 13- ,(2016) , 10.4230/LIPICS.MFCS.2016.85
Sebastian Siebertz, Reconfiguration on nowhere dense graph classes Electronic Journal of Combinatorics. ,vol. 25, pp. 3- 24 ,(2018) , 10.37236/7458
Fahad Panolan, Sebastian Siebertz, Eduard Eiben, Amer E. Mouawad, Mithilesh Kumar, Lossy Kernels for Connected Dominating Set on Sparse Graphs symposium on theoretical aspects of computer science. ,vol. 96, pp. 15- ,(2018) , 10.4230/LIPICS.STACS.2018.29
Zdeněk Dvořák, On distance ‐dominating and ‐independent sets in sparse graphs Journal of Graph Theory. ,vol. 91, pp. 162- 173 ,(2019) , 10.1002/JGT.22426
Roman Rabinovich, Sebastian Siebertz, Stephan Kreutzer, Polynomial kernels and wideness properties of nowhere dense graph classes symposium on discrete algorithms. ,vol. 15, pp. 1533- 1545 ,(2017) , 10.5555/3039686.3039786
Felix Reidl, Daniel Lokshtanov, Saket Saurabh, Markus Sortland Dregi, Marcin Pilipczuk, Fedor V. Fomin, Michal Pilipczuk, Pål Grønås Drange, Sebastian Siebertz, Stephan Kreutzer, Somnath Sikdar, Fernando Sánchez Villaamil, Kernelization and Sparseness: the case of Dominating Set symposium on theoretical aspects of computer science. ,vol. 47, pp. 14- ,(2016) , 10.4230/LIPICS.STACS.2016.31
Wojciech Nadara, Felix Reidl, Roman Rabinovich, Marcin Pilipczuk, Sebastian Siebertz, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness symposium on experimental and efficient algorithms. ,vol. 103, pp. 16- ,(2018) , 10.4230/LIPICS.SEA.2018.14
Wayne W. Zachary, An Information Flow Model for Conflict and Fission in Small Groups Journal of Anthropological Research. ,vol. 33, pp. 452- 473 ,(1977) , 10.1086/JAR.33.4.3629752