{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:58:21Z","timestamp":1743026301325,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031069000"},{"type":"electronic","value":"9783031069017"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-06901-7_6","type":"book-chapter","created":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T00:22:30Z","timestamp":1653610950000},"page":"70-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Faster Connectivity in\u00a0Low-Rank Hypergraphs via\u00a0Expander Decomposition"],"prefix":"10.1007","author":[{"given":"Calvin","family":"Beideman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagnik","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,27]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Beideman, C., Chandrasekaran, K., Mukhopadhyay, S., Nanongkai, D.: Faster connectivity in low-rank hypergraphs via expander decomposition. CoRR abs\/2011.08097 (2021)","DOI":"10.1007\/978-3-031-06901-7_6"},{"key":"6_CR2","unstructured":"Bernstein, A., et al.: Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR abs\/2004.08432 (2020)"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Gutenberg, M.P., Saranurak, T.: Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing. In: FOCS. IEEE Computer Society (2020)","DOI":"10.1109\/FOCS46700.2020.00108"},{"key":"6_CR4","unstructured":"Chandrasekaran, K., Xu, C., Yu, X.: Hypergraph $$k$$-cut in randomized polynomial time. Mathematical Programming (Preliminary version in SODA 2018), November 2019"},{"key":"6_CR5","unstructured":"Chekuri, C., Quanrud, K.: Isolating cuts, (Bi-)submodularity, and faster algorithms for connectivity. In: ICALP, pp. 50:1\u201350:20 (2021)"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Xu, C.: Computing minimum cuts in hypergraphs. In: SODA, pp. 1085\u20131100. SIAM (2017)","DOI":"10.1137\/1.9781611974782.70"},{"issue":"6","key":"6_CR7","doi-asserted-by":"publisher","first-page":"2118","DOI":"10.1137\/18M1163865","volume":"47","author":"C Chekuri","year":"2018","unstructured":"Chekuri, C., Xu, C.: Minimum cuts and sparsification in hypergraphs. SIAM J. Comput. 47(6), 2118\u20132156 (2018)","journal-title":"SIAM J. Comput."},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Gao, Y., Li, J., Nanongkai, D., Peng, R., Saranurak, T.: A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In: FOCS. IEEE Computer Society (2020)","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Forster, S., Nanongkai, D., Yang, L., Saranurak, T., Yingchareonthawornchai, S.: Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In: SODA, pp. 2046\u20132065. ACM\/SIAM (2020)","DOI":"10.1137\/1.9781611975994.126"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Fox, K., Panigrahi, D., Zhang, F.: Minimum cut and minimum k-cut in hypergraphs via branching contractions. In: SODA, pp. 881\u2013896. SIAM (2019)","DOI":"10.1137\/1.9781611975482.54"},{"key":"6_CR11","unstructured":"Gawrychowski, P., Mozes, S., Weimann, O.: Minimum cut in $$O(m \\log ^2 n)$$ time. In: ICALP, pp. 57:1\u201357:15 (2020)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Karger, D., Panigrahi, D.: Random contractions and sampling for hypergraph and hedge connectivity. In: SODA, pp. 1101\u20131114. ACM\/SIAM (2017)","DOI":"10.1137\/1.9781611974782.71"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Nowicki, K., Thorup, M.: Faster algorithms for edge connectivity via random 2-out contractions. In: SODA. ACM\/SIAM (2020)","DOI":"10.1137\/1.9781611975994.77"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Goranci, G., R\u00e4cke, H., Saranurak, T., Tan, Z.: The expander hierarchy and its applications to dynamic graph algorithms. In: SODA, pp. 2212\u20132228 (2021)","DOI":"10.1137\/1.9781611976465.132"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Rao, S., Wang, D.: Local flow partitioning for faster edge connectivity. In: SODA, pp. 1919\u20131938. ACM\/SIAM (2017)","DOI":"10.1137\/1.9781611974782.125"},{"key":"6_CR16","unstructured":"Karger, D.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In: SODA, pp. 21\u201330. ACM\/SIAM (1993)"},{"issue":"4","key":"6_CR17","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D Karger","year":"1996","unstructured":"Karger, D., Stein, C.: A new approach to the minimum cut problem. J. ACM 43(4), 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46\u201376 (2000). Announced at STOC 1996","DOI":"10.1145\/331605.331608"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: Deterministic edge connectivity in near-linear time. In: STOC, pp. 665\u2013674. ACM (2015)","DOI":"10.1145\/2746539.2746588"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: Deterministic edge connectivity in near-linear time. J. ACM 66(1), 4:1\u20134:50 (2019)","DOI":"10.1145\/3274663"},{"key":"6_CR21","unstructured":"Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Technical report B 96\u201302, Institute of Computer Science, Freie Universitat (1996)"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Kogan, D., Krauthgamer, R.: Sketching cuts in graphs and hypergraphs. In: ITCS, pp. 367\u2013376 (2015)","DOI":"10.1145\/2688073.2688093"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Li, J., Nanongkai, D., Panigrahi, D., Saranurak, T., Yingchareonthawornchai, S.: Vertex connectivity in poly-logarithmic max-flows (2021, unpublished)","DOI":"10.1145\/3406325.3451088"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Mak, W.K., Wong, M.D.F.: A fast hypergraph min-cut algorithm for circuit partitioning. Integr.: VLSI J. 30(1), 1\u201311 (2000)","DOI":"10.1016\/S0167-9260(00)00008-0"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Mukhopadhyay, S., Nanongkai, D.: Weighted min-cut: sequential, cut-query, and streaming algorithms. In: STOC, pp. 496\u2013509. ACM (2020)","DOI":"10.1145\/3357713.3384334"},{"issue":"1","key":"6_CR26","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discret. Math. 5(1), 54\u201366 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Saranurak, T.: Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and $${O}(n^{1\/2 - \\epsilon })$$-time. In: STOC, pp. 1122\u20131129. ACM (2017)","DOI":"10.1145\/3055399.3055447"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Saranurak, T., Yingchareonthawornchai, S.: Breaking quadratic time for small vertex connectivity and an approximation scheme. In: STOC, pp. 241\u2013252. ACM (2019)","DOI":"10.1145\/3313276.3316394"},{"issue":"1\u20132","key":"6_CR29","first-page":"3","volume":"82","author":"M Queyranne","year":"1998","unstructured":"Queyranne, M.: Minimizing symmetric submodular functions. Math. Program. 82(1\u20132), 3\u201312 (1998)","journal-title":"Math. Program."},{"key":"6_CR30","unstructured":"Rubinstein, A., Schramm, T., Weinberg, S.M.: Computing exact minimum cuts without knowing the graph. In: ITCS, pp. 39:1\u201339:16 (2018)"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Saranurak, T.: A simple deterministic algorithm for edge connectivity. In: SOSA. SIAM (2021)","DOI":"10.1137\/1.9781611976496.9"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Saranurak, T., Wang, D.: Expander decomposition and pruning: faster, stronger, and simpler. In: SODA, pp. 2616\u20132635. SIAM (2019)","DOI":"10.1137\/1.9781611975482.162"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Fully-dynamic minimum spanning forest with improved worst-case update time. In: STOC, pp. 1130\u20131143. ACM (2017)","DOI":"10.1145\/3055399.3055415"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-06901-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T23:21:08Z","timestamp":1727306468000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06901-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031069000","9783031069017"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06901-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"27 May 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Eindhoven","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.ipco2022.com\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"93","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}