تقرير
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
| العنوان: | Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs |
|---|---|
| المؤلفون: | López-Martínez, Andrés, Mukhopadhyay, Sagnik, Nanongkai, Danupon |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon}$ for any constant $\epsilon>0$, our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability. Its work matches the best $O(m \log n)$ runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by $O(\log^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 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching. Comment: Updates on this version: Minor corrections for the previous and our result |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2102.06565 |
| رقم الأكسشن: | edsarx.2102.06565 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |