Polynomial-time self-reducibility: theoretical motivations and practical results∗
From MaRDI portal
Publication:4009694
DOI10.1080/00207168908803783zbMath0825.68410OpenAlexW2116378217MaRDI QIDQ4009694
Michael A. Langston, Donna J. Brown, Michael R. Fellows
Publication date: 27 September 1992
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207168908803783
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Improved self-reduction algorithms for graphs with bounded treewidth, Obstruction set isolation for the gate matrix layout problem, Fixed-Parameter Tractability of Treewidth and Pathwidth, LP Formulations for Polynomial Optimization Problems, New limits of treewidth-based tractability in optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- Nonconstructive advances in polynomial-time complexity
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Graph minors. XIII: The disjoint paths problem
- Über eine Eigenschaft der ebenen Komplexe
- Knots and links in spatial graphs
- One-dimensional logic gate assignment and interval graphs
- A separator theorem for graphs of bounded genus
- Disjoint Paths—A Survey
- A polynomial algorithm for the min-cut linear arrangement of trees
- Nonconstructive tools for proving polynomial-time decidability
- The NP-completeness column: An ongoing guide