Login
- Titel:
A General Method to Speed Up Fixed-Parameter-Tractable Algorithms
- Dokumenttyp:
- Technical Report
- Autor(en):
- Rolf Niedermeier; Peter Rossmanith
- Abstract:
- A fixed-parameter-tractable algorithm, or FPT algorithm for short, gets an instance (I,k) as its input and has to decide whether (I,k) in L for some parameterized problem L. Many parameterized algorithms work in two stages: reduction to a problem kernel and bounded search tree. Their time complexity is then of the form O(p(|I|) + q(k) xi^k), where q(k) is the size of the problem kernel. We show how to modify these algorithms to obtain time complexity O(p(|I|)+xi^k), if q(k) is polynomial.
- Stichworte:
- parameterized complexity; fixed parameter tractability; bounded search tree; reduction to problem kernel
- Jahr:
- 1999
- Jahr / Monat:
- 1999-06-01 00:00:00
- Seiten/Umfang:
- 20
BibTeX