Subexponential Time Algorithms for Finding Small Tree and Path Decompositions

DOI10.1007/978-3-662-48350-3_16zbMath1422.68183arXiv1601.02415OpenAlexW2173182912WikidataQ59567464 ScholiaQ59567464MaRDI QIDQ3452781

Jesper Nederlof, Hans L. Bodlaender

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Multi-objective and goal programming (90C29) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Improved Lower Bounds for Graph Embedding Problems ⋮ Minimum size tree-decompositions ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ On the number of labeled graphs of bounded treewidth ⋮ Complexity of token swapping and its variants

Cites Work

• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?
• Partition into triangles on bounded degree graphs
• The number of trees
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Exact Algorithms for Intervalizing Colored Graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The complexity of satisfiability problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Minimum size tree-decompositions

This page was built for publication: Subexponential Time Algorithms for Finding Small Tree and Path Decompositions