A lower bound for treewidth and its consequences

DOI10.1007/3-540-59071-4_34MaRDI QIDQ6184352zbMATH OpenOpenAlexFDO

Authors Siddharthan Ramachandramurthi

Publication date 5 January 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59071-4_34

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The structure of obstructions to treewidth and pathwidth
• Treewidth lower bounds with brambles
• Algorithms – ESA 2005
• Treewidth computations. II. Lower bounds
• The Structure and Number of Obstructions to Treewidth

Cites work

• A characterization of partial 3-trees
• A linear time algorithm for finding tree-decompositions of small treewidth
• Complexity of Finding Embeddings in a k-Tree
• Easy problems for tree-decomposable graphs
• Forbidden minors characterization of partial 3-trees
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 176761 (Why is no real title available?)
• scientific article; zbMATH DE number 176762 (Why is no real title available?)
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• scientific article; zbMATH DE number 475617 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Narrowness, pathwidth, and their application in natural language processing
• Nonconstructive tools for proving polynomial-time decidability
• Obstruction set isolation for the gate matrix layout problem

Cited in

(8)

• A lower bound for tree resolution
• scientific article; zbMATH DE number 3864518 (Why is no real title available?)
• Lower Bounds for QBFs of Bounded Treewidth
• A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
• A managed Bayesian risk approach for decision making alternatives
• Default logic and bounded treewidth
• A general lower bound for collaborative tree exploration
• On the maximum cardinality search lower bound for treewidth

This page was built for publication: A lower bound for treewidth and its consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184352)