{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:20Z","timestamp":1750220180186,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538590","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"11-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs"],"prefix":"10.1145","author":[{"given":"Taisuke","family":"Izumi","sequence":"first","affiliation":[{"name":"Osaka University, Osaka, Japan"}]},{"given":"Naoki","family":"Kitamura","sequence":"additional","affiliation":[{"name":"Osaka University, Osaka, Japan"}]},{"given":"Takamasa","family":"Naruse","sequence":"additional","affiliation":[{"name":"Nagoya Institute of Technology, Aichi, Japan"}]},{"given":"Gregory","family":"Schwartzman","sequence":"additional","affiliation":[{"name":"Japan Advanced Institute of Science and Technology, Ishikawa, Japan"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Even in Sparse Networks. In 30th International Symposium on Distributed Computing (DISC). 29--42","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud , Keren Censor-Hillel , and Seri Khoury . 2016 . Near-Linear Lower Bounds for Distributed Distance Computations , Even in Sparse Networks. In 30th International Symposium on Distributed Computing (DISC). 29--42 . Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In 30th International Symposium on Distributed Computing (DISC). 29--42."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1145\/3212734.3212773"},{"key":"e_1_3_2_1_3_1","volume-title":"34th International Symposium on Distributed Computing (DISC). 37:1--37:18","author":"Ahmadi Mohamad","year":"2020","unstructured":"Mohamad Ahmadi and Fabian Kuhn . 2020 . Distributed maximum matching verification in CONGEST . In 34th International Symposium on Distributed Computing (DISC). 37:1--37:18 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.37 10.4230\/LIPIcs.DISC.2020.37 Mohamad Ahmadi and Fabian Kuhn. 2020. Distributed maximum matching verification in CONGEST. In 34th International Symposium on Distributed Computing (DISC). 37:1--37:18. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.37"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 32rd International Symposium on Distributed Computing (DISC). 6:1--6:17","author":"Ahmadi Mohamad","year":"2018","unstructured":"Mohamad Ahmadi , Fabian Kuhn , and Rotem Oshman . 2018 . Distributed approximate maximum matching in the congest model . In Proceedings of the 32rd International Symposium on Distributed Computing (DISC). 6:1--6:17 . https: \/\/doi.org\/10.4230\/LIPIcs.DISC.2018.6 10.4230\/LIPIcs.DISC.2018.6 Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. 2018. Distributed approximate maximum matching in the congest model. In Proceedings of the 32rd International Symposium on Distributed Computing (DISC). 6:1--6:17. https: \/\/doi.org\/10.4230\/LIPIcs.DISC.2018.6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1145\/3293611.3331597"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1145\/3087801.3087806"},{"key":"e_1_3_2_1_7_1","volume-title":"Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC). 7:1--7:16","author":"Becker Ruben","year":"2017","unstructured":"Ruben Becker , Andreas Karrenbauer , Sebastian Krinninger , and Christoph Lenzen . 2017 . Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC). 7:1--7:16 . Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC). 7:1--7:16."},{"key":"e_1_3_2_1_8_1","volume-title":"Proc. of 33rd International Symposium on Distributed Computing (DISC). 6:1--6:16","author":"Ben-Basat Ran","year":"2019","unstructured":"Ran Ben-Basat , Ken-ichi Kawarabayashi, and Gregory Schwartzman . 2019 . Parameterized Distributed Algorithms . In Proc. of 33rd International Symposium on Distributed Computing (DISC). 6:1--6:16 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.6 10.4230\/LIPIcs.DISC.2019.6 Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. 2019. Parameterized Distributed Algorithms. In Proc. of 33rd International Symposium on Distributed Computing (DISC). 6:1--6:16. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/3313276.3316326"},{"key":"e_1_3_2_1_10_1","volume-title":"Proc. of 34th International Symposium on Distributed Computing (DISC). 33:1--33:17","author":"Censor-Hillel Keren","year":"2020","unstructured":"Keren Censor-Hillel , Orr Fischer , Tzlil Gonen , Fran\u00e7ois Le Gall , Dean Leitersdorf , and Rotem Oshman . 2020 . Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs . In Proc. of 34th International Symposium on Distributed Computing (DISC). 33:1--33:17 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.33 10.4230\/LIPIcs.DISC.2020.33 Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, Fran\u00e7ois Le Gall, Dean Leitersdorf, and Rotem Oshman. 2020. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In Proc. of 34th International Symposium on Distributed Computing (DISC). 33:1--33:17. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.33"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/3382734"},{"volume-title":"Parameterized algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha? Pilipczuk, and Saket Saurabh . 2015. Parameterized algorithms . Springer . https:\/\/doi.org\/10.1007\/978--3--319--21275--3 10.1007\/978--3--319--21275--3 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha? Pilipczuk, and Saket Saurabh. 2015. Parameterized algorithms. Springer. https:\/\/doi.org\/10.1007\/978--3--319--21275--3","key":"e_1_3_2_1_12_1"},{"key":"e_1_3_2_1_13_1","volume-title":"Proc. of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 318--326","author":"Sarma Atish Das","year":"2012","unstructured":"Atish Das Sarma , Michael Dinitz , and Gopal Pandurangan . 2012 . Efficient Computation of Distance Sketches in Distributed Networks . In Proc. of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 318--326 . Atish Das Sarma, Michael Dinitz, and Gopal Pandurangan. 2012. Efficient Computation of Distance Sketches in Distributed Networks. In Proc. of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 318--326."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. of the 43rd Annual ACM Symposium on Theory of Computing. 363--372","author":"Sarma Atish Das","year":"2011","unstructured":"Atish Das Sarma , Stephan Holzer , Liah Kor , Amos Korman , Danupon Nanongkai , Gopal Pandurangan , David Peleg , and Roger Wattenhofer . 2011 . Distributed Verification and Hardness of Distributed Approximation . In Proc. of the 43rd Annual ACM Symposium on Theory of Computing. 363--372 . Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed Verification and Hardness of Distributed Approximation. In Proc. of the 43rd Annual ACM Symposium on Theory of Computing. 363--372."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/3055399.3055452"},{"key":"e_1_3_2_1_16_1","first-page":"1419","article-title":"Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth","volume":"14","author":"Fomin Fedor V.","year":"2017","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Michal Pilipczuk , Saket Saurabh , and Marcin Wrochna . 2017 . Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth . ACM Transactions on Algorithms 14 , 3 (2017), 1419 -- 1432 . https:\/\/doi.org\/10.1145\/3186898 10.1145\/3186898 Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, and Marcin Wrochna. 2017. Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth. ACM Transactions on Algorithms 14, 3 (2017), 1419--1432. https:\/\/doi.org\/10.1145\/3186898","journal-title":"ACM Transactions on Algorithms"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1109\/FOCS.2018.00071"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1145\/3087801.3087804"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1137\/1.9781611973099.91"},{"key":"e_1_3_2_1_20_1","volume-title":"Distance Labeling Scheme and Split Decomposition. Discrete Mathematics 273 (12","author":"Gavoille Cyril","year":"2003","unstructured":"Cyril Gavoille and Christophe Paul . 2003. Distance Labeling Scheme and Split Decomposition. Discrete Mathematics 273 (12 2003 ), 115--130. Cyril Gavoille and Christophe Paul. 2003. Distance Labeling Scheme and Split Decomposition. Discrete Mathematics 273 (12 2003), 115--130."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1137\/050635006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1016\/j.jalgor.2004.05.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1145\/2933057.2933109"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1137\/1.9781611974331.ch16"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1145\/3188745.3188948"},{"key":"e_1_3_2_1_26_1","volume-title":"Near-Optimal Distributed DFS in Planar Graphs. In 31st International Symposium on Distributed Computing (DISC 2017","volume":"91","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 ), Vol. 91 . 21:1--21:16. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.21 10.4230\/LIPIcs.DISC.2017.21 Mohsen Ghaffari and Merav Parter. 2017. Near-Optimal Distributed DFS in Planar Graphs. In 31st International Symposium on Distributed Computing (DISC 2017), Vol. 91. 21:1--21:16. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.21"},{"key":"e_1_3_2_1_27_1","volume-title":"Proc. of 34th International Symposium on Distributed Computing (DISC). 19:1--19:16","author":"Grossman Ofer","year":"2020","unstructured":"Ofer Grossman , Seri Khoury , and Ami Paz . 2020 . Improved Hardness of Approximation of Diameter in the CONGEST Model . In Proc. of 34th International Symposium on Distributed Computing (DISC). 19:1--19:16 . https:\/\/doi.org\/10.4230\/ LIPIcs.DISC.2020.19 Ofer Grossman, Seri Khoury, and Ami Paz. 2020. Improved Hardness of Approximation of Diameter in the CONGEST Model. In Proc. of 34th International Symposium on Distributed Computing (DISC). 19:1--19:16. https:\/\/doi.org\/10.4230\/ LIPIcs.DISC.2020.19"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/3212734.3212737"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_1_30_1","volume-title":"Proc. of 32nd International Symposium on Distributed Computing (DISC). 33:1--33:14","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler and Jason Li . 2018 . Faster Distributed Shortest Path Approximations via Shortcuts . In Proc. of 32nd International Symposium on Distributed Computing (DISC). 33:1--33:14 . Bernhard Haeupler and Jason Li. 2018. Faster Distributed Shortest Path Approximations via Shortcuts. In Proc. of 32nd International Symposium on Distributed Computing (DISC). 33:1--33:14."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_1_32_1","volume-title":"Proc. of the 48th Annual ACM Symposium on Theory of Computing (STOC). 489--498","author":"Henzinger Monika","year":"2016","unstructured":"Monika Henzinger , Sebastian Krinninger , and Danupon Nanongkai . 2016 . A Deterministic Almost-tight Distributed Algorithm for Approximating Singlesource Shortest Paths . In Proc. of the 48th Annual ACM Symposium on Theory of Computing (STOC). 489--498 . Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. A Deterministic Almost-tight Distributed Algorithm for Approximating Singlesource Shortest Paths. In Proc. of the 48th Annual ACM Symposium on Theory of Computing (STOC). 489--498."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1145\/2332432.2332504"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1109\/FOCS.2017.24"},{"key":"e_1_3_2_1_35_1","volume-title":"Proc. of 35th Symposium on Theoretical Aspects of Computer Science (STACS)","volume":"96","author":"Iwata Yoichi","year":"2018","unstructured":"Yoichi Iwata , Tomoaki Ogasawara , and Naoto Ohsaka . 2018 . On the Power of Tree-Depth for Fully Polynomial FPT Algorithms . In Proc. of 35th Symposium on Theoretical Aspects of Computer Science (STACS) , Vol. 96 . 41:1--41:14. https: \/\/doi.org\/10.4230\/LIPIcs.STACS.2018.41 10.4230\/LIPIcs.STACS.2018.41 Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2018. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In Proc. of 35th Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 96. 41:1--41:14. https: \/\/doi.org\/10.4230\/LIPIcs.STACS.2018.41"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1007\/978-3-319-14472-6_5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1016\/j.dam.2004.03.005"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1587\/transinf.2021EDP7083"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.5555\/1109557.1109666"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1145\/2488608.2488656"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1145\/2767386.2767398"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1145\/2484239.2484262"},{"key":"e_1_3_2_1_43_1","volume-title":"Distributed Treewidth Computation. arXiv","author":"Jason Li.","year":"2018","unstructured":"Jason Li. 2018. Distributed Treewidth Computation. arXiv ( 2018 ). arXiv:1805.10708 Jason Li. 2018. Distributed Treewidth Computation. arXiv (2018). arXiv:1805.10708"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1145\/3313276.3316358"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_45_1","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_46_1","first-page":"1","article-title":"An Experimental Study of the Treewidth of Real-World Graph Data. In ICDT (LIPIcs, Vol. 127)","volume":"12","author":"Maniu Silviu","year":"2019","unstructured":"Silviu Maniu , Pierre Senellart , and Suraj Jog . 2019 . An Experimental Study of the Treewidth of Real-World Graph Data. In ICDT (LIPIcs, Vol. 127) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 12 : 1 -- 12 :18. Silviu Maniu, Pierre Senellart, and Suraj Jog. 2019. An Experimental Study of the Treewidth of Real-World Graph Data. In ICDT (LIPIcs, Vol. 127). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 12:1--12:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_47_1","volume-title":"Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC). 565--573","author":"Nanongkai Danupon","year":"2014","unstructured":"Danupon Nanongkai . 2014 . Distributed Approximation Algorithms forWeighted Shortest Paths . In Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC). 565--573 . Danupon Nanongkai. 2014. Distributed Approximation Algorithms forWeighted Shortest Paths. In Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC). 565--573."},{"key":"e_1_3_2_1_48_1","volume-title":"Proc. of 34th International Symposium on Distributed Computing (DISC). 38:1--38:17","author":"Parter Merav","year":"2020","unstructured":"Merav Parter . 2020 . Distributed Planar Reachability in Nearly Optimal Time . In Proc. of 34th International Symposium on Distributed Computing (DISC). 38:1--38:17 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.38 10.4230\/LIPIcs.DISC.2020.38 Merav Parter. 2020. Distributed Planar Reachability in Nearly Optimal Time. In Proc. of 34th International Symposium on Distributed Computing (DISC). 38:1--38:17. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.38"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_49_1","DOI":"10.1007\/978-3-642-31585-5_58"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_50_1","DOI":"10.1137\/1.9781611977073.100"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"acronym":"SPAA '22","name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Philadelphia PA USA"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":50,"alternative-id":["10.1145\/3490148.3538590","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538590","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}