{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:42Z","timestamp":1750220382531,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2008422"],"award-info":[{"award-number":["CCF-2008422"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467908","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"295-305","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition"],"prefix":"10.1145","author":[{"given":"David G.","family":"Harris","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[{"name":"Boston College, Chestnut Hill, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoa T.","family":"Vu","sequence":"additional","affiliation":[{"name":"San Diego State University, San Diego, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"1","article-title":"The star arboricity of graphs","volume":"43","author":"Algor Ilan","year":"1989","unstructured":"Ilan Algor and Noga Alon . 1989 . The star arboricity of graphs . Discrete Mathematics 43 , 1 -- 3 (1989), 11--22. Ilan Algor and Noga Alon. 1989. The star arboricity of graphs. Discrete Mathematics 43, 1--3 (1989), 11--22.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305230"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90142-5"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0159"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Bahman Bahmani Ashish Goel and Kamesh Munagala. 2014. Efficient PrimalDual Graph Algorithms for MapReduce. In WAW (Lecture Notes in Computer Science 8882). 59--78.  Bahman Bahmani Ashish Goel and Kamesh Munagala. 2014. Efficient PrimalDual Graph Algorithms for MapReduce. In WAW (Lecture Notes in Computer Science 8882). 59--78.","DOI":"10.1007\/978-3-319-13123-8_6"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2534493"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Soheil Behnezhad Sebastian Brandt Mahsa Derakhshan Manuela Fischer MohammadTaghi Hajiaghayi Richard M. Karp and Jara Uitto. 2019. Massively Parallel Computation of Matching and MIS in Sparse Graphs. In PODC. 481--490.  Soheil Behnezhad Sebastian Brandt Mahsa Derakhshan Manuela Fischer MohammadTaghi Hajiaghayi Richard M. Karp and Jara Uitto. 2019. Massively Parallel Computation of Matching and MIS in Sparse Graphs. In PODC. 481--490.","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0528-0"},{"key":"e_1_3_2_2_12_1","volume-title":"A Fast Distributed Algorithm for Edge-Coloring. arXiv preprint arXiv:2006.15703","author":"Bernshteyn Anton","year":"2020","unstructured":"Anton Bernshteyn . 2020. A Fast Distributed Algorithm for Edge-Coloring. arXiv preprint arXiv:2006.15703 ( 2020 ). Anton Bernshteyn. 2020. A Fast Distributed Algorithm for Edge-Coloring. arXiv preprint arXiv:2006.15703 (2020)."},{"key":"e_1_3_2_2_13_1","volume-title":"Tsourakakis","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya , Monika Henzinger , Danupon Nanongkai , and Charalampos E . Tsourakakis . 2015 . Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In STOC. 173--182. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. 2015. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In STOC. 173--182."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Gerth St\u00f8lting Brodal and Rolf Fagerberg. 1999. Dynamic Representations of Sparse Graphs. In WADS. 342--351.  Gerth St\u00f8lting Brodal and Rolf Fagerberg. 1999. Dynamic Representations of Sparse Graphs. In WADS. 342--351.","DOI":"10.1007\/3-540-48447-7_34"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Y.-J. Chang Q. He W. Li S. Pettie and J. Uitto. 2018. The complexity of distributed edge coloring with small palettes. In SODA. 2633--2652.  Y.-J. Chang Q. He W. Li S. Pettie and J. Uitto. 2018. The complexity of distributed edge coloring with small palettes. In SODA. 2633--2652.","DOI":"10.1137\/1.9781611975031.168"},{"key":"e_1_3_2_2_16_1","volume-title":"APPROX (Lecture Notes in Computer Science","author":"Charikar Moses","year":"1913","unstructured":"Moses Charikar . 2000. Greedy approximation algorithms for finding dense components in a graph . In APPROX (Lecture Notes in Computer Science 1913 ). 84--95. Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In APPROX (Lecture Notes in Computer Science 1913). 84--95."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Michael Elkin and Ofer Neiman. 2016. Distributed Strong Diameter Network Decomposition: Extended Abstract. In PODC. 211--216.  Michael Elkin and Ofer Neiman. 2016. Distributed Strong Diameter Network Decomposition: Extended Abstract. In PODC. 211--216.","DOI":"10.1145\/2933057.2933094"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Michael Elkin Seth Pettie and Hsin-Hao Su. 2015. (2-1)-edge-coloring is much easier than maximal matching in the distributed setting. In SODA. 355--370.  Michael Elkin Seth Pettie and Hsin-Hao Su. 2015. (2-1)-edge-coloring is much easier than maximal matching in the distributed setting. In SODA. 355--370.","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_2_2_21_1","volume-title":"Woodruff","author":"Esfandiari Hossein","year":"2016","unstructured":"Hossein Esfandiari , MohammadTaghi Hajiaghayi , and David P . Woodruff . 2016 . Applications of Uniform Sampling: densest Subgraph and Beyond. In SPAA. 397-- 399. Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff. 2016. Applications of Uniform Sampling: densest Subgraph and Beyond. In SPAA. 397-- 399."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Manuela Fischer Mohsen Ghaffari and Fabian Kuhn. 2017. Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. In FOCS. 180--191.  Manuela Fischer Mohsen Ghaffari and Fabian Kuhn. 2017. Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. In FOCS. 180--191.","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_2_2_23_1","volume-title":"Gabow and Matthias Stallmann","author":"Harold","year":"1985","unstructured":"Harold N. Gabow and Matthias Stallmann . 1985 . Efficient algorithms for graphic matroid intersection and parity. In ICALP. 210--220. Harold N. Gabow and Matthias Stallmann. 1985. Efficient algorithms for graphic matroid intersection and parity. In ICALP. 210--220."},{"key":"e_1_3_2_2_24_1","volume-title":"Westermann","author":"Gabow Harold N.","year":"1992","unstructured":"Harold N. Gabow and Herbert H . Westermann . 1992 . Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica 7, 1 (1992), Article #465. Harold N. Gabow and Herbert H. Westermann. 1992. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica 7, 1 (1992), Article #465."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari David G. Harris and Fabian Kuhn. 2018. On Derandomizing Local Distributed Algorithms. In FOCS. 662--673.  Mohsen Ghaffari David G. Harris and Fabian Kuhn. 2018. On Derandomizing Local Distributed Algorithms. In FOCS. 662--673.","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari Juho Hirvonen Fabian Kuhn and Yannic Maus. 2018. Improved distributed -coloring. In PODC. 427--436.  Mohsen Ghaffari Juho Hirvonen Fabian Kuhn and Yannic Maus. 2018. Improved distributed -coloring. In PODC. 427--436.","DOI":"10.1145\/3212734.3212764"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari Fabian Kuhn and Yannic Maus. 2017. On the complexity of local distributed graph problems. In STOC. 784--797.  Mohsen Ghaffari Fabian Kuhn and Yannic Maus. 2017. On the complexity of local distributed graph problems. In STOC. 784--797.","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari Fabian Kuhn Yannic Maus and Jara Uitto. 2018. Deterministic Distributed Edge-coloring with Fewer Colors. In STOC. 418--430.  Mohsen Ghaffari Fabian Kuhn Yannic Maus and Jara Uitto. 2018. Deterministic Distributed Edge-coloring with Fewer Colors. In STOC. 418--430.","DOI":"10.1145\/3212734.3212764"},{"key":"e_1_3_2_2_30_1","first-page":"2201","article-title":"Improved Parallel Algorithms for Density-Based Network Clustering","volume":"97","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari , Silvio Lattanzi , and Slobodan Mitrovi?. 2019 . Improved Parallel Algorithms for Density-Based Network Clustering . In ICML , Vol. 97. 2201 -- 2210 . Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovi?. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In ICML, Vol. 97. 2201--2210.","journal-title":"ICML"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari and Hsin-Hao Su. 2017. Distributed Degree Splitting Edge Coloring and Orientations. In SODA. 2505--2523.  Mohsen Ghaffari and Hsin-Hao Su. 2017. Distributed Degree Splitting Edge Coloring and Orientations. In SODA. 2505--2523.","DOI":"10.1137\/1.9781611974782.166"},{"volume-title":"On High Spatial Reuse Link Scheduling in STDMA Wireless Ad Hoc Networks. In IEEE Global Telecommunications Conference (GLOBALCOM). 736--741","author":"Gore A. D.","key":"e_1_3_2_2_33_1","unstructured":"A. D. Gore , A. Karandikar , and S. Jagabathula . 2007 . On High Spatial Reuse Link Scheduling in STDMA Wireless Ad Hoc Networks. In IEEE Global Telecommunications Conference (GLOBALCOM). 736--741 . A. D. Gore, A. Karandikar, and S. Jagabathula. 2007. On High Spatial Reuse Link Scheduling in STDMA Wireless Ad Hoc Networks. In IEEE Global Telecommunications Conference (GLOBALCOM). 736--741."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Anupam Gupta Amit Kumar and Cliff Stein. 2014. Maintaining Assignments Online: Matching Scheduling and Flows. In SODA. 468--479.  Anupam Gupta Amit Kumar and Cliff Stein. 2014. Maintaining Assignments Online: Matching Scheduling and Flows. In SODA. 468--479.","DOI":"10.1137\/1.9781611973402.35"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(65)90340-6"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279241"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.26.186"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Samir Khuller and Barna Saha. 2009. On Finding Dense Subgraphs. In ICALP. 597--608.  Samir Khuller and Barna Saha. 2009. On Finding Dense Subgraphs. In ICALP. 597--608.","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Tsvi Kopelowitz Robert Krauthgamer Ely Porat and Shay Solomon. 2014. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. In ICALP. 532--543.  Tsvi Kopelowitz Robert Krauthgamer Ely Porat and Shay Solomon. 2014. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. In ICALP. 532--543.","DOI":"10.1007\/978-3-662-43951-7_45"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Lukasz Kowalik. 2006. Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures. In ISAAC. 557--566.  Lukasz Kowalik. 2006. Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures. In ISAAC. 557--566.","DOI":"10.1007\/11940128_56"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Fabian Kuhn. 2020. Faster Deterministic Distributed Coloring Through Recursive List Coloring. In SODA. 1244--1259.  Fabian Kuhn. 2020. Faster Deterministic Distributed Coloring Through Recursive List Coloring. In SODA. 1244--1259.","DOI":"10.1137\/1.9781611975994.76"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_3_2_2_44_1","volume-title":"Vu","author":"McGregor Andrew","year":"2015","unstructured":"Andrew McGregor , David Tench , Sofya Vorotnikova , and Hoa T . Vu . 2015 . Densest Subgraph in Dynamic Graph Streams. In MFCS (2) (Lecture Notes in Computer Science , Vol. 9235). Springer, 472-- 482 . Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. 2015. Densest Subgraph in Dynamic Graph Streams. In MFCS (2) (Lecture Notes in Computer Science, Vol. 9235). Springer, 472--482."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.222924"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.701"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"crossref","unstructured":"V\u00e1clav Rozho and Mohsen Ghaffari. 2020. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In STOC. 350--363.  V\u00e1clav Rozho and Mohsen Ghaffari. 2020. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In STOC. 350--363.","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_2_51_1","volume-title":"DISC (Lecture Notes in Computer Science","volume":"165","author":"Sarma Atish Das","year":"2012","unstructured":"Atish Das Sarma , Ashwin Lall , Danupon Nanongkai , and Amitabh Trehan . 2012 . Dense Subgraphs on Dynamic Networks . In DISC (Lecture Notes in Computer Science , Vol. 7611). Springer, 151-- 165 . Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan. 2012. Dense Subgraphs on Dynamic Networks. In DISC (Lecture Notes in Computer Science, Vol. 7611). Springer, 151--165."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"crossref","unstructured":"Saurabh Sawlani and Junxing Wang. 2020. Near-Optimal Fully Dynamic Densest Subgraph. In STOC. 181--193.  Saurabh Sawlani and Junxing Wang. 2020. Near-Optimal Fully Dynamic Densest Subgraph. In STOC. 181--193.","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1784"},{"key":"e_1_3_2_2_54_1","unstructured":"Jessica Shi Laxman Dhulipala and Julian Shun. 2020. Parallel Clique Counting and Peeling Algorithms. arXiv:2002.10047 [cs.DS] arXiv:2002.10047.  Jessica Shi Laxman Dhulipala and Julian Shun. 2020. Parallel Clique Counting and Peeling Algorithms. arXiv:2002.10047 [cs.DS] arXiv:2002.10047."},{"key":"e_1_3_2_2_55_1","first-page":"1","article-title":"Distributed Dense Subgraph Detection and Low Outdegree Orientation","volume":"15","author":"Su Hsin-Hao","year":"2020","unstructured":"Hsin-Hao Su and Hoa T. Vu . 2020 . Distributed Dense Subgraph Detection and Low Outdegree Orientation . In DISC. 15 : 1 -- 15 :18. Hsin-Hao Su and Hoa T. Vu. 2020. Distributed Dense Subgraph Detection and Low Outdegree Orientation. In DISC. 15:1--15:18.","journal-title":"DISC."},{"key":"e_1_3_2_2_56_1","volume-title":"Vu","author":"Su Hsin-Hao","year":"2019","unstructured":"Hsin-Hao Su and Hoa T . Vu . 2019 . Towards the Locality of Vizing's Theorem. In STOC. 355--364. Hsin-Hao Su and Hoa T. Vu. 2019. Towards the Locality of Vizing's Theorem. In STOC. 355--364."},{"key":"e_1_3_2_2_57_1","first-page":"25","article-title":"On an estimate of the chromatic class of a graph","volume":"3","author":"Vizing Vadim G.","year":"1964","unstructured":"Vadim G. Vizing . 1964 . On an estimate of the chromatic class of a graph . Diskret. Analiz 3 , 7 (1964), 25 -- 30 . Vadim G. Vizing. 1964. On an estimate of the chromatic class of a graph. Diskret. Analiz 3, 7 (1964), 25--30.","journal-title":"Diskret. Analiz"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467908","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":56,"alternative-id":["10.1145\/3465084.3467908","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467908","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}