A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911098477740032 |
|---|---|
| author | Bourneuf, Romain Planken, Tim |
| author_facet | Bourneuf, Romain Planken, Tim |
| contents | The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connected graphs, yielding a canonical tree-decomposition that decomposes the graph into its triconnected components. In 1973, Hopcroft and Tarjan introduced a linear-time algorithm to compute the Tutte-decomposition. Cunningham and Edmonds later established a structural characterization of the Tutte-decomposition via totally-nested 2-separations. We present a conceptually simple algorithm based on this characterization, which computes the Tutte-decomposition in linear time. Our algorithm first computes all totally-nested 2-separations and then builds the Tutte-decomposition from them.
Along the way, we derive new structural results on the structure of totally-nested 2-separations in 2-connected graphs using a novel notion of stability, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06212 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Structural Linear-Time Algorithm for Computing the Tutte Decomposition Bourneuf, Romain Planken, Tim Data Structures and Algorithms Discrete Mathematics Combinatorics The block-cut tree decomposes a connected graph along its cutvertices, displaying its 2-connected components. The Tutte-decomposition extends this idea to 2-separators in 2-connected graphs, yielding a canonical tree-decomposition that decomposes the graph into its triconnected components. In 1973, Hopcroft and Tarjan introduced a linear-time algorithm to compute the Tutte-decomposition. Cunningham and Edmonds later established a structural characterization of the Tutte-decomposition via totally-nested 2-separations. We present a conceptually simple algorithm based on this characterization, which computes the Tutte-decomposition in linear time. Our algorithm first computes all totally-nested 2-separations and then builds the Tutte-decomposition from them. Along the way, we derive new structural results on the structure of totally-nested 2-separations in 2-connected graphs using a novel notion of stability, which may be of independent interest. |
| title | A Structural Linear-Time Algorithm for Computing the Tutte Decomposition |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2508.06212 |