Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Some Prospects forEfficient Fixed Parameter Algorithms

Rolf NiedermeierContact Information

(5)  Wilhelm-Schickard-Institut für Informatik, UniversitÄt Tübingen, Sand 13, D-72076 Tübingen, Fed. Rep. of Germany
Abstract
Recent time has seen quite some progress in the development of exponential time algorithms for NP-hard problems, where the base of the exponential term is fairly small. These developments are also tightly related to the theory of fixed parameter tractability. In this incomplete survey, we explain some basic techniques in the design of efficient fixed parameter algorithms, discuss deficiencies of parameterized complexity theory, and try to point out some future research challenges. The focus of this paper is on the design of efficient algorithms and not on a structural theory of parameterized complexity. Moreover, our emphasis will be laid on two exemplifying issues: Vertex Cover and MaxSat problems.
Supported by a Feodor Lynen fellowship of the Alexander von Humboldt-Stiftung, Bonn, and the Center for Discrete Mathematics, Theoretical Computer Science and Applications (DIMATIA), Prague. Author’s address in 1998: DIMATIA MFF UK, Charles University, Malostranské námĚstí 25, 118 00 Praha 1, Czech Republic.

Contact Information Rolf Niedermeier
Email: bdniedermr@informatik.uni-tuebingen.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)