Polynomial-time self-reducibility: theoretical motivations and practical results∗

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

Mathematics Subject Classification ID

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

Related Items (5)

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

This page was built for publication: Polynomial-time self-reducibility: theoretical motivations and practical results^∗