{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:24Z","timestamp":1781078304581,"version":"3.54.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,7]],"date-time":"2015-09-07T00:00:00Z","timestamp":1441584000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00446-015-0251-x","type":"journal-article","created":{"date-parts":[[2015,9,7]],"date-time":"2015-09-07T00:16:11Z","timestamp":1441584971000},"page":"39-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A distributed low tree-depth decomposition algorithm for bounded expansion classes"],"prefix":"10.1007","volume":"29","author":[{"given":"J.","family":"Ne\u0161et\u0159il","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0724-3729","authenticated-orcid":false,"given":"P. Ossona","family":"de Mendez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,9,7]]},"reference":[{"key":"251_CR1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distrib. Comput. 22, 363\u2013379 (2010)","journal-title":"Distrib. Comput."},{"key":"251_CR2","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed $$(\\Delta +1)$$ ( \u0394 + 1 ) -coloring in linear (in $$\\Delta $$ \u0394 ) time. SIAM J. Comput. 43, 72\u201395 (2014)","journal-title":"SIAM J. Comput."},{"key":"251_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Deogun, J., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z. (1995) Rankings of graphs. In: Graph-Theoretic Concepts in Computer Science (Lecture notes in computer science), vol. 903\/1995. Springer, pp. 292\u2013304","DOI":"10.1007\/3-540-59071-4_56"},{"key":"251_CR4","doi-asserted-by":"crossref","unstructured":"Deogun, J., Kloks, T., Kratsch, D., M\u00fcller, H. (1994) On vertex ranking for permutation and other graphs. In: Enjalbert, P., Mayr, E., Wagner, K. (eds.), Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science (Lecture notes in computer science), vol.\u00a0775. Springer, pp.\u00a0747\u2013758","DOI":"10.1007\/3-540-57785-8_187"},{"key":"251_CR5","unstructured":"Dvo\u0159\u00e1k, Z.: Asymptotical structure of combinatorial objects, PhD thesis, Charles University, Faculty of Mathematics and Physics (2007)"},{"key":"251_CR6","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1016\/j.ejc.2012.12.004","volume":"34","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z.: Constant-factor approximation of domination number in sparse graphs. Eur. J. Combin. 34, 833\u2013840 (2013)","journal-title":"Eur. J. Combin."},{"key":"251_CR7","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1\u013e, D.: Algorithms for classes of graphs with bounded expansion, Lecture Notes in Computer Science, 5911 LNCS, pp.\u00a017\u201332 (2010)","DOI":"10.1007\/978-3-642-11409-0_2"},{"key":"251_CR8","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1\u013e, D., Thomas, R.: Deciding first-order properties for sparse graphs. In: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp.\u00a0133\u2013142. (2010)","DOI":"10.1109\/FOCS.2010.20"},{"key":"251_CR9","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1\u013e, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs, J. ACM, 60:5 Article 36 (2013)","DOI":"10.1145\/2499483"},{"key":"251_CR10","unstructured":"Dvo\u0159\u00e1k, Z., Kupec, M., T\u016fma, V.: Dynamic data structure for tree-depth decomposition. arXiv:1307.2863 [cs.DS]. July 2013"},{"key":"251_CR11","doi-asserted-by":"crossref","unstructured":"Gajarsk\u00fd, J., Hlin\u011bn\u00fd, P., Obdr\u017e\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., S\u00e1nchez\u00a0Villamil, F., Sikdar, S.: Kernelization using structural parameters on sparse graph classes In: ESA 2013. Lecture Notes in Computer Science, vol. 8125, pp. 529\u2013540. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40450-4_45"},{"key":"251_CR12","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0020-0190(87)90169-4","volume":"25","author":"AV Goldberg","year":"1987","unstructured":"Goldberg, A.V., Plotkin, S.A.: Parallel $$(\\Delta +1)$$ ( \u0394 + 1 ) -coloring of constant-degree graphs. Inf. Process. Lett. 25, 241\u2013245 (1987)","journal-title":"Inf. Process. Lett."},{"key":"251_CR13","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, pp.\u00a0181\u2013206. (2011)","DOI":"10.1090\/conm\/558\/11051"},{"key":"251_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914, New York, NY, USA, 2014, ACM, pp.\u00a089\u201398 (2014)","DOI":"10.1145\/2591796.2591851"},{"key":"251_CR15","volume-title":"Distributed Computing Through Combinatorial Topology","author":"M Herlihy","year":"2013","unstructured":"Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann Publishers Inc, San Francisc, USA (2013)"},{"key":"251_CR16","doi-asserted-by":"crossref","unstructured":"Kazana, W., Segoufin, L.: Enumeration of first-order queries on classes of structures with bounded expansion. In: Proceedings of the 16th International Conference on Database Theory, pp.\u00a010\u201320 (2013)","DOI":"10.1145\/2463664.2463667"},{"key":"251_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pp.\u00a07\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"key":"251_CR18","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R. (2010) Minimum dominating set approximation in graphs of bounded arboricity. In: Lynch, N., Shvartsman, A. (eds.) Distributed Computing (Lecture notes in computer science) vol.\u00a06343. Springer, Berlin Heidelberg, pp. 510\u2013524","DOI":"10.1007\/978-3-642-15763-9_48"},{"key":"251_CR19","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21, 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"251_CR20","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P. (2005) The grad of a graph and classes with bounded expansion. In: Raspaud, A., Delmas, O. (eds.), 7th International Colloquium on Graph Theory (Electronic notes in discrete mathematics), vol.\u00a022. Elsevier, pp.\u00a0101\u2013106","DOI":"10.1016\/j.endm.2005.06.018"},{"key":"251_CR21","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P. (2006) Linear time low tree-width partitions and algorithmic consequences. In: STOC\u201906. Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM Press, pp.\u00a0391\u2013400","DOI":"10.1145\/1132516.1132575"},{"key":"251_CR22","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27, 1022\u20131041 (2006)","journal-title":"Eur. J. Comb."},{"key":"251_CR23","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. decompositions. Eur. J. Comb. 29, 760\u2013776 (2008)","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"251_CR24","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/j.ejc.2006.07.014","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion II. algorithmic aspects. Eur. J. Comb. 29, 777\u2013791 (2008)","journal-title":"Eur. J. Comb."},{"key":"251_CR25","doi-asserted-by":"crossref","first-page":"1126","DOI":"10.1016\/j.ejc.2011.03.007","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J.: Ossona de Mendez, P.: How many F\u2019s are there in G? Eur. J. Comb. 32, 1126\u20131141 (2011)","journal-title":"Eur. J. Comb."},{"key":"251_CR26","volume-title":"Sparsity (Graphs, Structures, and Algorithms), vol.\u00a028 of Algorithms and Combinatorics","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity (Graphs, Structures, and Algorithms), vol.\u00a028 of Algorithms and Combinatorics. Springer, Berlin (2012)"},{"key":"251_CR27","unstructured":"Ne\u0161et\u0159il, J., Ossona\u00a0de Mendez, P. (2015) On first-order definable colorings. In: Ne\u0161et\u0159il, J., Pellegrini, M. (eds.), Geometry, Structure and Randomness in Combinatorics, vol.\u00a018 of Publications of the Scuola Normale Superiore, CRM Series, Edizioni della Normale, pp.\u00a099\u2013122"},{"key":"251_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-015-1569-7","volume":"31","author":"J Ne\u0161et\u0159il","year":"2015","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: On low tree-depth decompositions. Graphs Comb. 31, 1\u201323 (2015)","journal-title":"Graphs Comb."},{"key":"251_CR29","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P., Wood, D.: Characterizations and examples of graph classes with bounded expansion. Eur. J. Comb. 33, 350\u2013373 (2012)","journal-title":"Eur. J. Comb."},{"key":"251_CR30","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"251_CR31","doi-asserted-by":"crossref","unstructured":"Sch\u00e4ffer, A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33, 91\u201396 (1989\/90)","DOI":"10.1016\/0020-0190(89)90161-0"},{"key":"251_CR32","doi-asserted-by":"crossref","unstructured":"Szegedy, M., Vishwanathan, S. (1993) Locality based graph coloring. In: Proceedings 25th ACM Symposium on Theory of Computing, pp.\u00a0201\u2013207","DOI":"10.1145\/167088.167156"},{"key":"251_CR33","doi-asserted-by":"crossref","first-page":"4614","DOI":"10.1016\/j.disc.2009.02.028","volume":"309","author":"D Yang","year":"2009","unstructured":"Yang, D.: Generalization of transitive fraternal augmentations for directed graphs and its applications. Discrete Math. 309, 4614\u20134623 (2009)","journal-title":"Discrete Math."},{"key":"251_CR34","doi-asserted-by":"crossref","first-page":"5562","DOI":"10.1016\/j.disc.2008.03.024","volume":"309","author":"X Zhu","year":"2009","unstructured":"Zhu, X.: Colouring graphs with bounded generalized colouring number. Discrete Math. 309, 5562\u20135568 (2009)","journal-title":"Discrete Math."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0251-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-015-0251-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0251-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T02:50:44Z","timestamp":1567133444000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-015-0251-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,7]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["251"],"URL":"https:\/\/doi.org\/10.1007\/s00446-015-0251-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,7]]}}}