Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
- Publikationstyp:
- Kapitel
- Metadaten:
-
- Autoren
- Ernst Althaus
- Sarah Ziegler
- DOI
- 10.1007/978-3-030-63072-0_6
- ISBN-13
- 9783030630713
- Online publication date
- 2020
- Paginierung
- 67 - 78
- Buchtitel
- AIRO Springer Series
- Datum der Veröffentlichung
- 2021
- Status
- Published
- Herausgeber
- Springer International Publishing
- Herausgeber URL
- http://dx.doi.org/10.1007/978-3-030-63072-0_6
- Datum der Datenerfassung
- 2021
- Titel
- Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
Datenquelle: Crossref
- Andere Metadatenquellen:
-
- Abstract
- In 1996, Bodlaender showed the celebrated result that an optimal tree decomposition of a graph of bounded treewidth can be found in linear time. The algorithm is based on an algorithm of Bodlaender and Kloks that computes an optimal tree decomposition given a non-optimal tree decomposition of bounded width. Both algorithms, in particular the second, are hardly accessible. We present the second algorithm in a much simpler way in this paper and refer to an extended version for the first. In our description of the second algorithm, we start by explaining how all tree decompositions of subtrees defined by the nodes of the given tree decomposition can be enumerated. We group tree decompositions into equivalence classes depending on the current node of the given tree decomposition, such that it suffices to enumerate one tree decomposition per equivalence class and, for each node of the given tree decomposition, there are only a constant number of classes which can be represented in constant space.
- Autoren
- Ernst Althaus
- Sarah Ziegler
- DOI
- 10.1007/978-3-030-63072-0_6
- Editoren
- Claudio Gentile
- Giuseppe Stecca
- Paolo Ventura
- ISBN-13
- 978-3-030-63072-0
- Paginierung
- 67 - 78
- Buchtitel
- Graphs and Combinatorial Optimization: from Theory to Applications: CTW2020 Proceedings
- Ort der Veröffentlichung
- Cham
- Datum der Veröffentlichung
- 2021
- Herausgeber
- Springer International Publishing
- Herausgeber URL
- https://doi.org/10.1007/978-3-030-63072-0_6
- Datum der Datenerfassung
- 2022
- Titel
- Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
Datenquelle: Manual
- Beziehungen:
- Eigentum von