Improved self-reduction algorithms for graphs with bounded treewidth

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

Hans L. Bodlaender

Publication date: 1 August 2000

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90018-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Seeing Arboretum for the (partial k-) Trees, Fixed-Parameter Tractability of Treewidth and Pathwidth

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