A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910564078321664 |
|---|---|
| author | Tsin, Yung H. |
| author_facet | Tsin, Yung H. |
| contents | A linear-time algorithm for generating auxiliary subgraphs for the 3-edge-connected components of a connected multigraph is presented. The algorithm uses an innovative graph contraction operation and makes only one pass over the graph. By contrast, the previously best-known algorithms make multiple passes over the graph to decompose it into its 2-edge-connected components or 2-vertex-connected components, then its 3-edge-connected components or 3-vertex-connected components, and then construct a cactus representation for the 2-cuts to generate the auxiliary subgraphs for the 3-edge-connected components. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_13827 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs Tsin, Yung H. Data Structures and Algorithms A linear-time algorithm for generating auxiliary subgraphs for the 3-edge-connected components of a connected multigraph is presented. The algorithm uses an innovative graph contraction operation and makes only one pass over the graph. By contrast, the previously best-known algorithms make multiple passes over the graph to decompose it into its 2-edge-connected components or 2-vertex-connected components, then its 3-edge-connected components or 3-vertex-connected components, and then construct a cactus representation for the 2-cuts to generate the auxiliary subgraphs for the 3-edge-connected components. |
| title | A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2309.13827 |