1999 | OriginalPaper | Buchkapitel
Some Other W[1]-Hardness Results
verfasst von : R. G. Downey, M. R. Fellows
Erschienen in: Parameterized Complexity
Verlag: Springer New York
Enthalten in: Professional Book Archive
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
In this chapter, we will explore some further W[1]-hardness and completeness results. These examples are taken from logic, formal language theory, and from combinatorial problems arising from molecular biology. We also look at further applications of the theory to arenas such as algebra and number theory in the Exercises, where problems such as the following are proven to be W[1]-hard (and the first two are in W[2]):