Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Fixed-Parameter Tractability, A Prehistory,
verfasst von : Michael A. Langston
Erschienen in: The Multivariate Algorithmic Revolution and Beyond
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Many of the foundational parameterized tenets discussed in this festschrift actually predate by over a decade the first systematic treatments of fixed-parameter tractability. In this frank, firsthand account I will, to the best of my recollection, describe some of the earliest research avenues Mike Fellows and I pursued that would turn out later to be highly relevant to parameterized complexity. Although we did not know it at the time, these were the origins and formative years of this burgeoning new field. Readers unfamiliar with the history of fixed-parameter tractability may be surprised to learn that its initial motivations arose from, of all things, automation and optimization for integrated circuit design.