Using Cycles and Scaling in Parallel Algorithms
We introduce the technique of decomposing an undirected graph by finding a maximal set of edge-disjoint cycles. We give a parallel algorithm to find this decomposition in O(log n) time on (m+ n)/log n processors. We then use this decomposition to to give the first efficient parallel algorithm for...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149682 |
| _version_ | 1811077983016845312 |
|---|---|
| author | Stein, Clifford |
| author2 | Shmoys, David |
| author_facet | Shmoys, David Stein, Clifford |
| author_sort | Stein, Clifford |
| collection | MIT |
| description | We introduce the technique of decomposing an undirected graph by finding a maximal set of edge-disjoint cycles. We give a parallel algorithm to find this decomposition in O(log n) time on (m+ n)/log n processors. We then use this decomposition to to give the first efficient parallel algorithm for finding an approximation to a minimum cycle cover. |
| first_indexed | 2024-09-23T10:51:32Z |
| id | mit-1721.1/149682 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:51:32Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1496822023-03-30T03:58:35Z Using Cycles and Scaling in Parallel Algorithms Stein, Clifford Shmoys, David We introduce the technique of decomposing an undirected graph by finding a maximal set of edge-disjoint cycles. We give a parallel algorithm to find this decomposition in O(log n) time on (m+ n)/log n processors. We then use this decomposition to to give the first efficient parallel algorithm for finding an approximation to a minimum cycle cover. 2023-03-29T15:16:26Z 2023-03-29T15:16:26Z 1989-08 https://hdl.handle.net/1721.1/149682 20900185 MIT-LCS-TR-457 application/pdf |
| spellingShingle | Stein, Clifford Using Cycles and Scaling in Parallel Algorithms |
| title | Using Cycles and Scaling in Parallel Algorithms |
| title_full | Using Cycles and Scaling in Parallel Algorithms |
| title_fullStr | Using Cycles and Scaling in Parallel Algorithms |
| title_full_unstemmed | Using Cycles and Scaling in Parallel Algorithms |
| title_short | Using Cycles and Scaling in Parallel Algorithms |
| title_sort | using cycles and scaling in parallel algorithms |
| url | https://hdl.handle.net/1721.1/149682 |
| work_keys_str_mv | AT steinclifford usingcyclesandscalinginparallelalgorithms |