A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910982563954688 |
|---|---|
| author | Alejandro-Soto, J. A. Trejo-Sanchez, Joel Antonio Segura, Carlos |
| author_facet | Alejandro-Soto, J. A. Trejo-Sanchez, Joel Antonio Segura, Carlos |
| contents | This work proposes \textsc{H-Td}, a practical linear-time algorithm for computing an optimal-width tree decomposition of Halin graphs. Unlike state-of-the-art methods based on reduction rules or separators, \textsc{H-Td} exploits the structural properties of Halin graphs. Although two theoretical linear-time algorithms exist that can be applied to graphs of treewidth three, no practical implementation has been made publicly available. Furthermore, extending reduction-based approaches to partial $k$-trees with $k > 3$ results in increasingly complex rules that are challenging to implement. This motivates the exploration of alternative strategies that leverage structural insights specific to certain graph classes. Experimental validation against the winners of the Parameterized Algorithms and Computational Experiments Challenge (PACE) 2017 and the treewidth library \texttt{libtw} demonstrates the advantage of \textsc{H-Td} when the input is known to be a Halin graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02346 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs Alejandro-Soto, J. A. Trejo-Sanchez, Joel Antonio Segura, Carlos Data Structures and Algorithms This work proposes \textsc{H-Td}, a practical linear-time algorithm for computing an optimal-width tree decomposition of Halin graphs. Unlike state-of-the-art methods based on reduction rules or separators, \textsc{H-Td} exploits the structural properties of Halin graphs. Although two theoretical linear-time algorithms exist that can be applied to graphs of treewidth three, no practical implementation has been made publicly available. Furthermore, extending reduction-based approaches to partial $k$-trees with $k > 3$ results in increasingly complex rules that are challenging to implement. This motivates the exploration of alternative strategies that leverage structural insights specific to certain graph classes. Experimental validation against the winners of the Parameterized Algorithms and Computational Experiments Challenge (PACE) 2017 and the treewidth library \texttt{libtw} demonstrates the advantage of \textsc{H-Td} when the input is known to be a Halin graph. |
| title | A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.02346 |