Fixed-parameter tractability, a prehistory

DOI10.1007/978-3-642-30891-8_1MaRDI QIDQ2908528zbMATHOpenAlexFDO

Authors Michael A. Langston

Publication date 5 September 2012

Published in The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-30891-8_1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) History of computer science (68-03)

Recommendations

• The birth and early years of parameterized complexity
• A basic parameterized complexity primer
• Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows
• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 2080999

Cites work

• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Disjoint Paths—A Survey
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Nonconstructive advances in polynomial-time complexity
• Nonconstructive tools for proving polynomial-time decidability
• Obstruction set isolation for the gate matrix layout problem
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• The vertex separation number of a graph equals its path-width

Cited in

(3)

• The birth and early years of parameterized complexity
• About one characteristic initial value problem with prehistory and its investigation
• scientific article; zbMATH DE number 512844 (Why is no real title available?)

This page was built for publication: Fixed-parameter tractability, a prehistory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908528)