{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:13Z","timestamp":1750220833404,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":82,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1991\/19"],"award-info":[{"award-number":["1991\/19"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400248","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"395-406","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence"],"prefix":"10.1145","author":[{"given":"Lazar","family":"Milenkovi\u0107","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.006"},{"key":"e_1_3_2_1_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1974","unstructured":"Alfred V. Aho , John E. Hopcroft , and Jeffrey D . Ullman . 1974 . The Design and Analysis of Computer Algorithms .Addison-Wesley. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms .Addison-Wesley."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.98"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087581"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188922"},{"key":"e_1_3_2_1_8_1","volume-title":"Proc. of the 46th ICALP. 17:1--17:17","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi and Shay Solomon . 2019 . When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time . In Proc. of the 46th ICALP. 17:1--17:17 . Sepehr Assadi and Shay Solomon. 2019. When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time. In Proc. of the 46th ICALP. 17:1--17:17."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212751"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993825"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087812"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00082"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338529"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-38919-2_22"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976014.14"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.7"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.61"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998925"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_25_1","volume-title":"Proc. of the 30th SODA. Also posted on CoRR, abs\/1805","author":"Bhattacharya Sayan","year":"2019","unstructured":"Sayan Bhattacharya and Janardhan Kulkarni . 2019 (to appear). Deterministically Maintaining a (2+\u03b5)-Approximate Minimum Vertex Cover in O(1\/(\u03b5)(^2 )) Amortized Update Time . In Proc. of the 30th SODA. Also posted on CoRR, abs\/1805 .03498, 2018. Sayan Bhattacharya and Janardhan Kulkarni. 2019 (to appear). Deterministically Maintaining a (2+\u03b5)-Approximate Minimum Vertex Cover in O(1\/(\u03b5)(^2 )) Amortized Update Time. In Proc. of the 30th SODA. Also posted on CoRR, abs\/1805.03498, 2018."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.48"},{"key":"e_1_3_2_1_27_1","volume-title":"Karnin","author":"Censor-Hillel Keren","year":"2016","unstructured":"Keren Censor-Hillel , Elad Haramaty , and Zohar S . Karnin . 2016 . Optimal Dynamic Distributed MIS. In Proc. of the PODC. 217--226. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. 2016. Optimal Dynamic Distributed MIS. In Proc. of the PODC. 217--226."},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. of the 45th ICALP. 33:1--33:14","author":"Charikar Moses","year":"2018","unstructured":"Moses Charikar and Shay Solomon . 2018 . Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier . In Proc. of the 45th ICALP. 33:1--33:14 . Moses Charikar and Shay Solomon. 2018. Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. In Proc. of the 45th ICALP. 33:1--33:14."},{"key":"e_1_3_2_1_30_1","volume-title":"Surveys in Combinatorics, 2005 [invited lectures from the Twentieth British Combinatorial Conference","author":"Chudnovsky Maria","year":"2005","unstructured":"Maria Chudnovsky and Paul D. Seymour . 2005. The structure of claw-free graphs . In Surveys in Combinatorics, 2005 [invited lectures from the Twentieth British Combinatorial Conference , Durham, UK , July 2005 ]. Cambridge University Press, 153--171. Maria Chudnovsky and Paul D. Seymour. 2005. The structure of claw-free graphs. In Surveys in Combinatorics, 2005 [invited lectures from the Twentieth British Combinatorial Conference, Durham, UK, July 2005]. Cambridge University Press, 153--171."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-21.3.219"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_2_1_34_1","volume-title":"Distributed Maximum Matching in Bounded Degree Graphs. CoRR","author":"Even Guy","year":"2014","unstructured":"Guy Even , Moti Medina , and Dana Ron . 2014. Distributed Maximum Matching in Bounded Degree Graphs. CoRR , Vol. abs\/ 1407 .7882 ( 2014 ). Guy Even, Moti Medina, and Dana Ron. 2014. Distributed Maximum Matching in Bounded Degree Graphs. CoRR, Vol. abs\/1407.7882 (2014)."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00045-3"},{"volume-title":"Proc. of the 26th FOCS. 490--495","author":"Galil Zvi","key":"e_1_3_2_1_36_1","unstructured":"Zvi Galil and Victor Y. Pan . 1985. Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC . In Proc. of the 26th FOCS. 490--495 . Zvi Galil and Victor Y. Pan. 1985. Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC. In Proc. of the 26th FOCS. 490--495."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281111"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_40_1","volume-title":"Proc. of the 32nd DISC. 30:1--30:12","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2018 . Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping . In Proc. of the 32nd DISC. 30:1--30:12 . Mohsen Ghaffari and Fabian Kuhn. 2018. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In Proc. of the 32nd DISC. 30:1--30:12."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.2"},{"key":"e_1_3_2_1_42_1","volume-title":"Proc. of the 42nd STOC. 39--46","author":"Goel Ashish","year":"2010","unstructured":"Ashish Goel , Michael Kapralov , and Sanjeev Khanna . 2010 . Perfect matchings in o(n log n) time in regular bipartite graphs . In Proc. of the 42nd STOC. 39--46 . Ashish Goel, Michael Kapralov, and Sanjeev Khanna. 2010. Perfect matchings in o(n log n) time in regular bipartite graphs. In Proc. of the 42nd STOC. 39--46."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"volume-title":"Proc. of 17th ESA, Amos Fiat and Peter Sanders (Eds.). 361--372","author":"Magn\u00fa","key":"e_1_3_2_1_46_1","unstructured":"Magn\u00fa s M. Halld\u00f3 rsson. 2009. Wireless Scheduling with Power Control . In Proc. of 17th ESA, Amos Fiat and Peter Sanders (Eds.). 361--372 . Magn\u00fa s M. Halld\u00f3 rsson. 2009. Wireless Scheduling with Power Control. In Proc. of 17th ESA, Amos Fiat and Peter Sanders (Eds.). 361--372."},{"key":"e_1_3_2_1_47_1","volume-title":"Halld\u00f3 rsson and Christian Konrad","author":"Magn\u00fa","year":"2015","unstructured":"Magn\u00fa s M. Halld\u00f3 rsson and Christian Konrad . 2015 . Distributed Large Independent Sets in One Round on Bounded-Independence Graphs. In Proc. of DISC. 559--572. Magn\u00fa s M. Halld\u00f3 rsson and Christian Konrad. 2015. Distributed Large Independent Sets in One Round on Bounded-Independence Graphs. In Proc. of DISC. 559--572."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1031-8"},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. of the 9th SODA. 219--225","author":"Hanckowiak Michal","year":"1998","unstructured":"Michal Hanckowiak , Michal Karonski , and Alessandro Panconesi . 1998 . On the Distributed Complexity of Computing Maximal Matchings . In Proc. of the 9th SODA. 219--225 . Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. 1998. On the Distributed Complexity of Computing Maximal Matchings. In Proc. of the 9th SODA. 219--225."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1941201224"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"volume-title":"Flows in Networks","author":"Ford Lester Randolph","key":"e_1_3_2_1_54_1","unstructured":"Lester Randolph Ford Jr . and Delbert Ray Fulkerson . 1965. Flows in Networks . Princeton University Press , Princeton, New Jersey. Lester Randolph Ford Jr. and Delbert Ray Fulkerson. 1965. Flows in Networks. Princeton University Press, Princeton, New Jersey."},{"key":"e_1_3_2_1_55_1","first-page":"199","article-title":"On the translocation of masses","volume":"37","author":"Kantorovich Leonid V","year":"1942","unstructured":"Leonid V Kantorovich . 1942 . On the translocation of masses . In Dokl. Akad. Nauk. USSR (NS) , Vol. 37. 199 -- 201 . Leonid V Kantorovich. 1942. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), Vol. 37. 199--201.","journal-title":"Dokl. Akad. Nauk. USSR (NS)"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210397"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.121"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22148"},{"volume-title":"Proc. of the 22nd STOC. 352--358","author":"Karp Richard M.","key":"e_1_3_2_1_59_1","unstructured":"Richard M. Karp , Umesh V. Vazirani , and Vijay V. Vazirani . 1990. An Optimal Algorithm for On-line Bipartite Matching . In Proc. of the 22nd STOC. 352--358 . Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An Optimal Algorithm for On-line Bipartite Matching. In Proc. of the 22nd STOC. 352--358."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767405"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-007-0045-6"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35668-1_24"},{"key":"e_1_3_2_1_64_1","volume-title":"Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston.","author":"Lawler Eugene L","year":"1976","unstructured":"Eugene L Lawler . 1976 . Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston. New York (1976). Eugene L Lawler. 1976. Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston. New York (1976)."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15763-9_48"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_68_1","volume-title":"Proc. of the 32nd DISC. 37:1--37:17","author":"Mashreghi Ali","year":"2018","unstructured":"Ali Mashreghi and Valerie King . 2018 . Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model . In Proc. of the 32nd DISC. 37:1--37:17 . Ali Mashreghi and Valerie King. 2018. Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. In Proc. of the 32nd DISC. 37:1--37:17."},{"key":"e_1_3_2_1_69_1","volume-title":"Proc. of the 33rd DISC. 49:1--49:3.","author":"Mashreghi Ali","year":"2019","unstructured":"Ali Mashreghi and Valerie King . 2019 . Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication . In Proc. of the 33rd DISC. 49:1--49:3. Ali Mashreghi and Valerie King. 2019. Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. In Proc. of the 33rd DISC. 49:1--49:3."},{"key":"e_1_3_2_1_70_1","volume-title":"Vazirani","author":"Micali Silvio","year":"1980","unstructured":"Silvio Micali and Vijay V . Vazirani . 1980 . An O(sqrt((vert)v(vert)) (vert)E(vert)) Algorithm for Finding Maximum Matching in General Graphs. In Proc. of the 21st FOCS. IEEE Computer Society , 17--27. Silvio Micali and Vijay V. Vazirani. 1980. An O(sqrt((vert)v(vert)) (vert)E(vert)) Algorithm for Finding Maximum Matching in General Graphs. In Proc. of the 21st FOCS. IEEE Computer Society, 17--27."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488703"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.88"},{"key":"e_1_3_2_1_73_1","first-page":"502","article-title":"Finding the maximum cut in a graph","volume":"10","author":"Orlova GI","year":"1972","unstructured":"GI Orlova . 1972 . Finding the maximum cut in a graph . Engineering Cybernetics , Vol. 10 (1972), 502 -- 506 . GI Orlova. 1972. Finding the maximum cut in a graph. Engineering Cybernetics, Vol. 10 (1972), 502--506.","journal-title":"Engineering Cybernetics"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055449"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch17"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch51"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400758"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_1_81_1","volume-title":"Proc. of the 9th ITCS. 52:1--52:19","author":"Solomon Shay","year":"2018","unstructured":"Shay Solomon . 2018 . Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs . In Proc. of the 9th ITCS. 52:1--52:19 . Shay Solomon. 2018. Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. In Proc. of the 9th ITCS. 52:1--52:19."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289039"},{"key":"e_1_3_2_1_83_1","volume-title":"An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm. CoRR","author":"Vazirani Vijay V.","year":"2012","unstructured":"Vijay V. Vazirani . 2012. An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm. CoRR , Vol. abs\/ 1210 .4594 ( 2012 ). Vijay V. Vazirani. 2012. An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm. CoRR, Vol. abs\/1210.4594 (2012)."},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"crossref","unstructured":"David Wajc. 2020. Rounding Dynamic Matchings Against an Adaptive Adversary. In STOC. To appear. Also in CoRR abs\/1911.05545.  David Wajc. 2020. Rounding Dynamic Matchings Against an Adaptive Adversary. In STOC. To appear. Also in CoRR abs\/1911.05545.","DOI":"10.1145\/3357713.3384258"}],"event":{"name":"SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures","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"],"location":"Virtual Event USA","acronym":"SPAA '20"},"container-title":["Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400248","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:35Z","timestamp":1750202015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":82,"alternative-id":["10.1145\/3350755.3400248","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400248","relation":{},"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2020-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}