Improved self-reduction algorithms for graphs with bounded treewidth

DOI10.1016/0166-218X(94)90018-3zbMath0941.68652WikidataQ59567996 ScholiaQ59567996MaRDI QIDQ1336622

Hans L. Bodlaender

Publication date: 1 August 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. VI. Disjoint paths across a disc
• Nonconstructive advances in polynomial-time complexity
• Min Cut is NP-complete for edge weighted trees
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Black-white pebbles and graph separation
• Graph minors. X: Obstructions to tree-decomposition
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Searching and pebbling
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithms finding tree-decompositions of graphs
• Easy problems for tree-decomposable graphs
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• The complexity of searching a graph
• Nonconstructive tools for proving polynomial-time decidability
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Polynomial-time self-reducibility: theoretical motivations and practical results^∗
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• An algebraic theory of graph reduction
• A linear time algorithm for finding tree-decompositions of small treewidth
• Recontamination does not help to search a graph