A lower bound for treewidth and its consequences

DOI10.1007/3-540-59071-4_34zbMath1528.68319OpenAlexW1531100498MaRDI QIDQ6184352

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden minors characterization of partial 3-trees
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Narrowness, pathwidth, and their application in natural language processing
• Obstruction set isolation for the gate matrix layout problem
• Graph minors. XIII: The disjoint paths problem
• Graph minors. IV: Tree-width and well-quasi-ordering
• Easy problems for tree-decomposable graphs
• A characterization of partial 3-trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Nonconstructive tools for proving polynomial-time decidability
• A linear time algorithm for finding tree-decompositions of small treewidth