𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The structure of obstructions to treewidth and pathwidth

✍ Scribed by Janka Chlebíková

Book ID
104444454
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
107 KB
Volume
3
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Pathwidth and Treewidth of Cographs
The Pathwidth and Treewidth of Cographs
✍ Bodlaender, Hans L.; Möhring, Rolf H. 📂 Article 📅 1993 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 940 KB
Efficient and Constructive Algorithms fo
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
✍ Hans L. Bodlaender; Ton Kloks 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 373 KB

In this paper we give, for all constants k, l, explicit algorithms that, given a graph Ž . Gs V,E with a tree-decomposition of G with treewidth at most l, decide Ž . whether the treewidth or pathwidth of G is at most k, and, if so, find a Ž . tree-decomposition or path-decomposition of G of width at