Optimal tree decompositions revisited: a simpler linear-time FPT algorithm

DOI10.1007/978-3-030-63072-0_6zbMath1479.05294arXiv1912.09144OpenAlexW2995115154MaRDI QIDQ2056889

Sarah Ziegler, Ernst Althaus

Publication date: 8 December 2021

Full work available at URL: https://arxiv.org/abs/1912.09144

zbMATH Keywords

tree decompositionsparametrized complexitysimplified description

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Optimal tree decompositions revisited: a simpler linear-time FPT algorithm ⋮ Measuring power in coalitional games with friends, enemies and allies

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Parametrized complexity theory.
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Optimal tree decompositions revisited: a simpler linear-time FPT algorithm