{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:39Z","timestamp":1773704799583,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"DOI":"10.1145\/3583668.3594604","type":"proceedings-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T22:28:38Z","timestamp":1686954518000},"page":"55-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112406"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_32"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248381"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933084"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326170"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.13"},{"key":"e_1_3_2_1_8_1","volume-title":"Local certification of graph decompositions and applications to minor-free classes. CoRR abs\/2108.00059","author":"Bousquet Nicolas","year":"2021","unstructured":"Nicolas Bousquet, Laurent Feuilloley, and Th\u00e9o Pierron. 2021. Local certification of graph decompositions and applications to minor-free classes. CoRR abs\/2108.00059 (2021). arXiv:2108.00059 https:\/\/arxiv.org\/abs\/2108.00059"},{"key":"e_1_3_2_1_9_1","volume-title":"Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. arXiv preprint arXiv:2304.04699","author":"Chang Yi-Jun","year":"2023","unstructured":"Yi-Jun Chang. 2023. Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. arXiv preprint arXiv:2304.04699 (2023)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446330"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00043"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538423"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_24"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-14472-6_4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.12.027"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933094"},{"key":"e_1_3_2_1_19_1","volume-title":"Local certification of graphs on surfaces. arXiv preprint arXiv:2102.04133","author":"Esperet Louis","year":"2021","unstructured":"Louis Esperet and Benjamin L\u00e9v\u011bque. 2021. Local certification of graphs on surfaces. arXiv preprint arXiv:2102.04133 (2021)."},{"key":"e_1_3_2_1_20_1","volume-title":"An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor","author":"Fakcharoenphol Jittat","unstructured":"Jittat Fakcharoenphol and Kunal Talwar. 2003. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, Sanjeev Arora, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Amit Sahai (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 36--46."},{"key":"e_1_3_2_1_21_1","volume-title":"Local Certification of Graphs with Bounded Genus. CoRR abs\/2007.08084","author":"Feuilloley Laurent","year":"2020","unstructured":"Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Eric R\u00e9mila, and Ioan Todinca. 2020. Local Certification of Graphs with Bounded Genus. CoRR abs\/2007.08084 (2020). arXiv:2007.08084 https:\/\/arxiv.org\/abs\/2007.08084"},{"key":"e_1_3_2_1_22_1","volume-title":"Compact distributed certification of planar graphs. Algorithmica","author":"Feuilloley Laurent","year":"2021","unstructured":"Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, \u00c9ric R\u00e9mila, and Ioan Todinca. 2021. Compact distributed certification of planar graphs. Algorithmica (2021), 1--30."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch97"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933109"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467935"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings 32nd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"16","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Jason Li. 2018. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In Proceedings 32nd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1--31:16."},{"key":"e_1_3_2_1_30_1","volume-title":"31st International Symposium on Distributed Computing (DISC","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Merav Parter. 2017. Near-optimal distributed DFS in planar graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795292208"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212737"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.33"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538590"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_1_39_1","volume-title":"Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2","author":"Lenzen Christoph","year":"2013","unstructured":"Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2013. Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2 (2013), 119--137."},{"key":"e_1_3_2_1_40_1","volume-title":"Leveraging Linial's Locality Limit","author":"Lenzen Christoph","unstructured":"Christoph Lenzen and Roger Wattenhofer. 2008. Leveraging Linial's Locality Limit. In Distributed Computing, Gadi Taubenfeld (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 394--407."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00382-3"},{"key":"e_1_3_2_1_42_1","volume-title":"Distributed treewidth computation. arXiv preprint arXiv:1805.10708","author":"Jason Li.","year":"2018","unstructured":"Jason Li. 2018. Distributed treewidth computation. arXiv preprint arXiv:1805.10708 (2018)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316358"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_45_1","volume-title":"Low diameter graph decompositions. Combinatorica 13, 4 (01","author":"Linial Nathan","year":"1993","unstructured":"Nathan Linial and Michael Saks. 1993. Low diameter graph decompositions. Combinatorica 13, 4 (01 Dec 1993), 441--454."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.67"},{"key":"e_1_3_2_1_48_1","volume-title":"Distributed Planar Reachability in Nearly Optimal Time. In 34th International Symposium on Distributed Computing (DISC","author":"Parter Merav","year":"2020","unstructured":"Merav Parter. 2020. Distributed Planar Reachability in Nearly Optimal Time. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.52"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.008"}],"event":{"name":"PODC '23: 2023 ACM Symposium on Principles of Distributed Computing","location":"Orlando FL USA","acronym":"PODC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"]},"container-title":["Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:55Z","timestamp":1750178275000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":54,"alternative-id":["10.1145\/3583668.3594604","10.1145\/3583668"],"URL":"https:\/\/doi.org\/10.1145\/3583668.3594604","relation":{},"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"2023-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}