Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.001.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially ...
More
This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is a vividly developing field, with a growing list of applications in various contexts such as network analysis or bioinformatics. The book emphasizes algorithmic techniques over computational complexity theory. It is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essentials of parameterized hardness theory with a focus on W[1]-hardness which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.Less
This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is a vividly developing field, with a growing list of applications in various contexts such as network analysis or bioinformatics. The book emphasizes algorithmic techniques over computational complexity theory. It is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essentials of parameterized hardness theory with a focus on W[1]-hardness which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.
Rolf Niedermeier
- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0003
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter introduces basic concepts which are necessary for an understanding of this subject, beginning with a close look at parameterized algorithmics. It briefly highlights the central aspects ...
More
This chapter introduces basic concepts which are necessary for an understanding of this subject, beginning with a close look at parameterized algorithmics. It briefly highlights the central aspects of the theory, defining parameterized problems, fixed-parameter tractability, parameterized reductions, and the parameterized complexity class W[1] representing parameterized hardness. In addition, it also indicates the limitations of the theory, focussing on different sorts of combinatorial explosions.Less
This chapter introduces basic concepts which are necessary for an understanding of this subject, beginning with a close look at parameterized algorithmics. It briefly highlights the central aspects of the theory, defining parameterized problems, fixed-parameter tractability, parameterized reductions, and the parameterized complexity class W[1] representing parameterized hardness. In addition, it also indicates the limitations of the theory, focussing on different sorts of combinatorial explosions.
