Work-optimal parallel minimum cuts for non-sparse graphs
2021 (English)In: Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery (ACM) , 2021, p. 351-361Conference paper, Published paper (Refereed)
Abstract [en]
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For ≥ n^1+ϵ for any constant ϵ>0, our algorithm requires O(m łog n) work and O(łog^3 n) depth and succeeds with high probability. Its work matches the best O(m łog n) runtime for sequential algorithms [MN STOC'20; GMW SOSA'21]. This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by a O(łog^3 n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.
Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2021. p. 351-361
Keywords [en]
Approximation algorithms, Graph algorithms, Minimum cut, Orthogonal range searching, Parallel algorithms, Graph theory, Efficient approximation algorithms, High probability, Polylogarithmic, Range searching, Runtimes, Sequential algorithm, Sparse graphs
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-310408DOI: 10.1145/3409964.3461806Scopus ID: 2-s2.0-85109572907OAI: oai:DiVA.org:kth-310408DiVA, id: diva2:1648621
Conference
SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021.
Note
Part of proceedings ISBN: 978-1-4503-8070-6
QC 20220331
2022-03-312022-03-312022-06-25Bibliographically approved