Minimum size tree-decompositions

DOI10.1016/j.endm.2015.07.005zbMath1347.05158OpenAlexW1574061374WikidataQ62046026 ScholiaQ62046026MaRDI QIDQ5890931

Karol Suchan, Nicolas Nisse, Fatima Zahra Moataz, Bi Li

Publication date: 17 October 2016

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.005

zbMATH Keywords

treewidthNP-hardminimum size tree-decomposition

Mathematics Subject Classification ID

Trees (05C05) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Subexponential Time Algorithms for Finding Small Tree and Path Decompositions ⋮ Minimum size tree-decompositions

Cites Work

• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• On Linear Recognition of Tree-Width at Most Four
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Minimum size tree-decompositions