Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey

Bodlaender, Hans L.

doi:https://doi.org/10.1007/978-3-031-75409-8_1

Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey

Files

978-3-031-75409-8_1.pdf (447.43 KB)

Publication date

2025

Authors

Bodlaender, Hans

Editors

Kráľ, Daniel

Milanič, Martin

DOI

https://doi.org/10.1007/978-3-031-75409-8_1

Document Type

Part of book

Metadata

Show full item record

Collections

Utrecht University Repository

License

taverne

Abstract

This short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.

Keywords

Approximation, Graph Algorithms, Pathwidth, Treedepth, Treewidth, Taverne, Theoretical Computer Science, General Computer Science

Citation

Bodlaender, H L 2025, Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey. in D Kráľ & M Milanič (eds), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14760 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 3-18, 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024, Gozd Martuljek, Slovenia, 19/06/24. https://doi.org/10.1007/978-3-031-75409-8_1, conference

URI

https://dspace.library.uu.nl/handle/1874/482731