Improved self-reduction algorithms for graphs with bounded treewidth
From MaRDI portal
Publication:1336622
DOI10.1016/0166-218X(94)90018-3zbMath0941.68652OpenAlexW2098879666WikidataQ59567996 ScholiaQ59567996MaRDI QIDQ1336622
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
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
