Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913343207374848 |
|---|---|
| author | Gawrychowski, Paweł Wasylkiewicz, Mateusz |
| author_facet | Gawrychowski, Paweł Wasylkiewicz, Mateusz |
| contents | Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither constructive nor algorithmic, Biedl, Bose, Demaine, and Lubiw [J. Algorithms 38(1)] showed how to implement a later constructive proof by Frink in $\mathcal{O}(n\log^{4}n)$ time using a fully dynamic 2-edge-connectivity structure. Then, Diks and Stańczyk [SOFSEM 2010] described a faster approach that only needs a fully dynamic connectivity structure and works in $\mathcal{O}(n\log^{2}n)$ time. Both algorithms, while reasonable simple, utilize non-trivial (2-edge-)connectivity structures. We show that this is not necessary, and in fact a structure for maintaining a dynamic tree, e.g. link-cut trees, suffices to obtain a simple $\mathcal{O}(n\log n)$ time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03856 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity Gawrychowski, Paweł Wasylkiewicz, Mateusz Data Structures and Algorithms Discrete Mathematics Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither constructive nor algorithmic, Biedl, Bose, Demaine, and Lubiw [J. Algorithms 38(1)] showed how to implement a later constructive proof by Frink in $\mathcal{O}(n\log^{4}n)$ time using a fully dynamic 2-edge-connectivity structure. Then, Diks and Stańczyk [SOFSEM 2010] described a faster approach that only needs a fully dynamic connectivity structure and works in $\mathcal{O}(n\log^{2}n)$ time. Both algorithms, while reasonable simple, utilize non-trivial (2-edge-)connectivity structures. We show that this is not necessary, and in fact a structure for maintaining a dynamic tree, e.g. link-cut trees, suffices to obtain a simple $\mathcal{O}(n\log n)$ time algorithm. |
| title | Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2405.03856 |