{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:00Z","timestamp":1770994080013,"version":"3.50.1"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T00:00:00Z","timestamp":1575936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Marie Sk\u0142odowska-Curie","award":["665778"],"award-info":[{"award-number":["665778"]}]},{"name":"European Research Council"},{"name":"ERC Consolidator Grant DISTRUCT","award":["648527"],"award-info":[{"award-number":["648527"]}]},{"name":"Recent trends in kernelization: theory and experimental evaluation"},{"name":"European Union's Horizon 2020 research and innovation programme"},{"name":"National Science Centre of Poland via POLONEZ grant","award":["UMO-2015\/19\/P\/ST6\/03998"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998"]}]},{"name":"Homing programme of the Foundation for Polish Science"},{"name":"European Union under the European Regional Development Fund"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            The notions of\n            <jats:italic>bounded expansion<\/jats:italic>\n            and\n            <jats:italic>nowhere denseness<\/jats:italic>\n            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\n            <jats:italic>generalized coloring numbers<\/jats:italic>\n            and the property of being\n            <jats:italic>uniformly quasi-wide<\/jats:italic>\n            . 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.\n          <\/jats:p>","DOI":"10.1145\/3368630","type":"journal-article","created":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T13:21:36Z","timestamp":1575984096000},"page":"1-34","source":"Crossref","is-referenced-by-count":6,"title":["Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness"],"prefix":"10.1145","volume":"24","author":[{"given":"Wojciech","family":"Nadara","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roman","family":"Rabinovich","sequence":"additional","affiliation":[{"name":"Lehrstuhl f\u00fcr Logic und Semantik, Technische Universit\u00e4t Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Royal Holloway University of London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Gephi Datasets. Retrieved from https:\/\/github.com\/gephi\/gephi\/wiki\/Datasets.  [n.d.]. Gephi Datasets. Retrieved from https:\/\/github.com\/gephi\/gephi\/wiki\/Datasets."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. LEDA. Retrieved from http:\/\/www.algorithmic-solutions.com\/leda\/index.htm.  [n.d.]. LEDA. Retrieved from http:\/\/www.algorithmic-solutions.com\/leda\/index.htm."},{"key":"e_1_2_1_3_1","unstructured":"2018. Recent trends in kernelization: Theory and experimental evaluation\u2014project website. Retrieved from http:\/\/kernelization-experiments.mimuw.edu.pl.  2018. Recent trends in kernelization: Theory and experimental evaluation\u2014project website. Retrieved from http:\/\/kernelization-experiments.mimuw.edu.pl."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 3rd International Workshop on Link Discovery. ACM, 36--43","author":"Lada","unstructured":"Lada A. Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: Divided they blog . In Proceedings of the 3rd International Workshop on Link Discovery. ACM, 36--43 . Lada A. Adamic and Natalie Glance. 2005. The political blogosphere and the 2004 US election: Divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery. ACM, 36--43."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210383"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_7_1","unstructured":"Vladimir Batagelj and Andrej Mrvar. 2006. Pajek datasets. Retrieved from http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/.  Vladimir Batagelj and Andrej Mrvar. 2006. Pajek datasets. Retrieved from http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000211"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645726.667215"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg340"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129081"},{"key":"e_1_2_1_17_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-81-322-0487-9_83"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.10.005"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909)","author":"Dawar Anuj","year":"2009","unstructured":"Anuj Dawar and Stephan Kreutzer . 2009 . Domination problems in nowhere-dense classes . In Proceedings of the IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909) . 157--168. Anuj Dawar and Stephan Kreutzer. 2009. Domination problems in nowhere-dense classes. In Proceedings of the IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909). 157--168."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916)","volume":"63","author":"Dell Holger","unstructured":"Holger Dell , Thore Husfeldt , Bart M. P. Jansen , Petteri Kaski , Christian Komusiewicz , and Frances A. Rosamond . 2017. The first parameterized algorithms and computational experiments challenge . In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916) , Vol. 63 . 30:1--30:9. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2017. The first parameterized algorithms and computational experiments challenge. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916), Vol. 63. 30:1--30:9."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9138-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993696"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2341-5"},{"key":"e_1_2_1_27_1","volume-title":"Somnath Sikdar, and Blair D. Sullivan.","author":"Demaine Erik D.","year":"2014","unstructured":"Erik D. Demaine , Felix Reidl , Peter Rossmanith , Fernando S\u00e1nchez Villaamil , Somnath Sikdar, and Blair D. Sullivan. 2014 . Structural sparsity of complex networks: Random graph models and linear algorithms. Retrieved from CoRR abs\/1406.2587 (2014). arxiv:1406.2587 Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando S\u00e1nchez Villaamil, Somnath Sikdar, and Blair D. Sullivan. 2014. Structural sparsity of complex networks: Random graph models and linear algorithms. Retrieved from CoRR abs\/1406.2587 (2014). arxiv:1406.2587"},{"key":"e_1_2_1_28_1","first-page":"25","article-title":"Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory","volume":"91","author":"DeVos Matt","year":"2004","unstructured":"Matt DeVos , Guoli Ding , Bogdan Oporowski , Daniel P. Sanders , Bruce Reed , Paul Seymour , and Dirk Vertigan . 2004 . Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory , Ser. B 91 , 1 (2004), 25 -- 41 . Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan. 2004. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory, Ser. B 91, 1 (2004), 25--41.","journal-title":"Ser. B"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2016","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Markus Sortland Dregi , Fedor V. Fomin , Stephan Kreutzer , Daniel Lokshtanov , Marcin Pilipczuk , Micha\u0142 Pilipczuk , Felix Reidl , Fernando S\u00e1nchez Villaamil , Saket Saurabh , Sebastian Siebertz , and Somnath Sikdar . 2016 . Kernelization and sparseness: The case of dominating set . In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) . 31:1--31:14. P\u00e5l Gr\u00f8n\u00e5s Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Micha\u0142 Pilipczuk, Felix Reidl, Fernando S\u00e1nchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916). 31:1--31:14."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22426"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS\u201918)","volume":"96","author":"Eiben Eduard","year":"2018","unstructured":"Eduard Eiben , Mithilesh Kumar , Amer E. Mouawad , Fahad Panolan , and Sebastian Siebertz . 2018 . Lossy kernels for connected dominating set on sparse graphs . In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS\u201918) . LIPIcs, Vol. 96 . 29:1--29:15. Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. 2018. Lossy kernels for connected dominating set on sparse graphs. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS\u201918). LIPIcs, Vol. 96. 29:1--29:15."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Eickmeyer Kord","year":"2017","unstructured":"Kord Eickmeyer , Archontia C. Giannopoulou , Stephan Kreutzer , O-joung Kwon, Micha\u0142 Pilipczuk , Roman Rabinovich , and Sebastian Siebertz . 2017 . Neighborhood complexity and kernelization for nowhere dense classes of graphs . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) . 63:1--63:14. Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Micha\u0142 Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2017. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). 63:1--63:14."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701361104"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201915)","volume":"9224","author":"Grohe Martin","year":"2015","unstructured":"Martin Grohe , Stephan Kreutzer , Roman Rabinovich , Sebastian Siebertz , and Konstantinos Stavropoulos . 2015 . Colouring and covering nowhere dense graphs . In Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201915) , Vol. 9224 . 325--338. Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. 2015. Colouring and covering nowhere dense graphs. In Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201915), Vol. 9224. 325--338."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2463667"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 1st Conference on Email and Anti-Spam (CEAS\u201904)","author":"Klimt Bryan","year":"2004","unstructured":"Bryan Klimt and Yiming Yang . 2004 . Introducing the Enron corpus . In Proceedings of the 1st Conference on Email and Anti-Spam (CEAS\u201904) . Bryan Klimt and Yiming Yang. 2004. Introducing the Enron corpus. In Proceedings of the 1st Conference on Email and Anti-Spam (CEAS\u201904)."},{"key":"e_1_2_1_43_1","volume-title":"The Stanford GraphBase: A Platform for Combinatorial Computing","author":"Knuth Donald Ervin","unstructured":"Donald Ervin Knuth . 1993. The Stanford GraphBase: A Platform for Combinatorial Computing . Vol. 37 . Addison-Wesley Reading . Donald Ervin Knuth. 1993. The Stanford GraphBase: A Platform for Combinatorial Computing. Vol. 37. Addison-Wesley Reading."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)","author":"Kreutzer Stephan","year":"2016","unstructured":"Stephan Kreutzer , Micha\u0142 Pilipczuk , Roman Rabinovich , and Sebastian Siebertz . 2016 . The generalised colouring numbers on classes of bounded expansion . In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916) . Stephan Kreutzer, Micha\u0142 Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2016. The generalised colouring numbers on classes of bounded expansion. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.100"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201918)","author":"Kun Jeremy","unstructured":"Jeremy Kun , Michael P. O\u2019Brien , and Blair D. Sullivan . 2018. Treedepth bounds in linear colorings . In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201918) . 331--343. Jeremy Kun, Michael P. O\u2019Brien, and Blair D. Sullivan. 2018. Treedepth bounds in linear colorings. In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201918). 331--343."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the International Web Observatory Workshop. 1343--1350","author":"Kunegis J\u00e9r\u00f4me","year":"2013","unstructured":"J\u00e9r\u00f4me Kunegis . 2013 . KONECT\u2014The Koblenz network collection . In Proceedings of the International Web Observatory Workshop. 1343--1350 . Retrieved from http:\/\/konect.uni-koblenz.de. J\u00e9r\u00f4me Kunegis. 2013. KONECT\u2014The Koblenz network collection. In Proceedings of the International Web Observatory Workshop. 1343--1350. Retrieved from http:\/\/konect.uni-koblenz.de."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975499.12"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_51_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.02.004"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00265-003-0651-y"},{"key":"e_1_2_1_54_1","volume-title":"Experimental evaluation of kernelization algorithms to dominating set. Retrieved from CoRR abs\/1811.07831","author":"Nadara Wojciech","year":"2018","unstructured":"Wojciech Nadara . 2018. Experimental evaluation of kernelization algorithms to dominating set. Retrieved from CoRR abs\/1811.07831 ( 2018 ). arxiv:1811.07831 Wojciech Nadara. 2018. Experimental evaluation of kernelization algorithms to dominating set. Retrieved from CoRR abs\/1811.07831 (2018). arxiv:1811.07831"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Wojciech Nadara Marcin Pilipczuk Felix Reidl Roman Rabinovich and Sebastian Siebertz. 2018. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. Code repository. Retrieved from https:\/\/bitbucket.org\/marcin_pilipczuk\/wcol-uqw-experiments.  Wojciech Nadara Marcin Pilipczuk Felix Reidl Roman Rabinovich and Sebastian Siebertz. 2018. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. Code repository. Retrieved from https:\/\/bitbucket.org\/marcin_pilipczuk\/wcol-uqw-experiments.","DOI":"10.1145\/3368630"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.019"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1278682204"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_2_1_62_1","volume-title":"Algorithms and Combinatorics","author":"Ne\u0161et\u0159il Jaroslav","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez . 2012. Sparsity\u2014Graphs, Structures, and Algorithms. Algorithms and Combinatorics , Vol. 28 . Springer . Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity\u2014Graphs, Structures, and Algorithms. Algorithms and Combinatorics, Vol. 28. Springer."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"e_1_2_1_66_1","volume-title":"Sullivan","author":"O\u2019Brien Michael P.","year":"2017","unstructured":"Michael P. O\u2019Brien and Blair D . Sullivan . 2017 . Experimental evaluation of counting subgraph isomorphisms in classes of bounded expansion. Retrieved from CoRR abs\/1712.06690 (2017). arxiv:1712.06690. Michael P. O\u2019Brien and Blair D. Sullivan. 2017. Experimental evaluation of counting subgraph isomorphisms in classes of bounded expansion. Retrieved from CoRR abs\/1712.06690 (2017). arxiv:1712.06690."},{"key":"e_1_2_1_67_1","volume-title":"Treewidth from Treedepth. Bachelor\u2019s thesis","author":"Oelschl\u00e4gel Tobias","unstructured":"Tobias Oelschl\u00e4gel . 2014. Treewidth from Treedepth. Bachelor\u2019s thesis . RWTH Aachen University , Germany . Tobias Oelschl\u00e4gel. 2014. Treewidth from Treedepth. Bachelor\u2019s thesis. RWTH Aachen University, Germany."},{"key":"e_1_2_1_68_1","volume-title":"Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Retrieved from CoRR abs\/1809.05675","author":"Pilipczuk Micha\u0142","year":"2018","unstructured":"Micha\u0142 Pilipczuk and Sebastian Siebertz . 2018. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Retrieved from CoRR abs\/1809.05675 ( 2018 ). arxiv:1809.05675. Micha\u0142 Pilipczuk and Sebastian Siebertz. 2018. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Retrieved from CoRR abs\/1809.05675 (2018). arxiv:1809.05675."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.91"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209178"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-100-2-101-107"},{"key":"e_1_2_1_73_1","volume-title":"Fernando S\u00e1nchez Villaamil, and Konstantinos Stavropoulos","author":"Reidl Felix","year":"2016","unstructured":"Felix Reidl , Fernando S\u00e1nchez Villaamil, and Konstantinos Stavropoulos . 2016 . Characterising bounded expansion by neighbourhood complexity. Retrieved from CoRR abs\/1603.09532 (2016). Felix Reidl, Fernando S\u00e1nchez Villaamil, and Konstantinos Stavropoulos. 2016. Characterising bounded expansion by neighbourhood complexity. Retrieved from CoRR abs\/1603.09532 (2016)."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39718-2_23"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.978369"},{"key":"e_1_2_1_76_1","unstructured":"Neil Robertson and Paul D. Seymour. 1982--2010. Graph minors I-XXII.  Neil Robertson and Paul D. Seymour. 1982--2010. Graph minors I-XXII."},{"key":"e_1_2_1_77_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915)","author":"Ryan","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization . In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915) . 4292--4293. Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u201915). 4292--4293."},{"key":"e_1_2_1_78_1","volume-title":"About Treedepth and Related Notions. Dissertation","author":"Villaamil Fernando S\u00e1nchez","unstructured":"Fernando S\u00e1nchez Villaamil . 2017. About Treedepth and Related Notions. Dissertation . RWTH Aachen University , Aachen . Retrieved from http:\/\/publications.rwth-aachen.de\/record\/709271. Fernando S\u00e1nchez Villaamil. 2017. About Treedepth and Related Notions. Dissertation. RWTH Aachen University, Aachen. Retrieved from http:\/\/publications.rwth-aachen.de\/record\/709271."},{"key":"e_1_2_1_79_1","first-page":"P3","article-title":"Reconfiguration on nowhere dense graph classes","volume":"25","author":"Siebertz Sebastian","year":"2018","unstructured":"Sebastian Siebertz . 2018 . Reconfiguration on nowhere dense graph classes . Electr. J. Comb. 25 , 3 (2018), P3 .24. Sebastian Siebertz. 2018. Reconfiguration on nowhere dense graph classes. Electr. J. Comb. 25, 3 (2018), P3.24.","journal-title":"Electr. J. Comb."},{"key":"e_1_2_1_80_1","volume-title":"C. R\u00e9gis, B. Lina, and P. Vanhems.","author":"Stehl\u00e9 Juliette","year":"2011","unstructured":"Juliette Stehl\u00e9 , N. Voirin , Alain Barrat , Ciro Cattuto , Lorenzo Isella , Jean-Fran\u00e7ois Pinton , Marco Quaggiotto , Wouter Van den Broeck , C. R\u00e9gis, B. Lina, and P. Vanhems. 2011 . High-resolution measurements of face-to-face contact patterns in a primary school. PLOS One 6, 8 (8 2011), e23176. Juliette Stehl\u00e9, N. Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-Fran\u00e7ois Pinton, Marco Quaggiotto, Wouter Van den Broeck, C. R\u00e9gis, B. Lina, and P. Vanhems. 2011. High-resolution measurements of face-to-face contact patterns in a primary school. PLOS One 6, 8 (8 2011), e23176."},{"key":"e_1_2_1_81_1","volume-title":"Proceedings of the 25th European Symposium on Algorithms (ESA\u201917)","volume":"87","author":"Tamaki Hisao","year":"2017","unstructured":"Hisao Tamaki . 2017 . Positive-instance driven dynamic programming for treewidth . In Proceedings of the 25th European Symposium on Algorithms (ESA\u201917) , Vol. 87 . 68:1--68:13. Hisao Tamaki. 2017. Positive-instance driven dynamic programming for treewidth. In Proceedings of the 25th European Symposium on Algorithms (ESA\u201917), Vol. 87. 68:1--68:13."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.06.019"},{"key":"e_1_2_1_83_1","volume-title":"Strogatz","author":"Watts Duncan J.","year":"1998","unstructured":"Duncan J. Watts and Steven H . Strogatz . 1998 . Collective dynamics of \u201csmall-world\u201d networks. Nature 393, 6684 (1998), 440. Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u201csmall-world\u201d networks. Nature 393, 6684 (1998), 440."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstb.1986.0056"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368630","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368630","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:42Z","timestamp":1750202622000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368630"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,10]]},"references-count":84,"alternative-id":["10.1145\/3368630"],"URL":"https:\/\/doi.org\/10.1145\/3368630","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,10]]}}}