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.
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.0014
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility ...
More
This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility results. In particular, polynomial-time approximation schemes are discussed in some detail, providing a link with parameterized complexity theory.Less
This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility results. In particular, polynomial-time approximation schemes are discussed in some detail, providing a link with parameterized complexity theory.
Oliver Johns
- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780191001628
- eISBN:
- 9780191775161
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780191001628.001.0001
- Subject:
- Physics, Atomic, Laser, and Optical Physics
This book provides an innovative and mathematically sound treatment of the foundations of analytical mechanics, and of the relation of classical mechanics to relativity and quantum theory. A ...
More
This book provides an innovative and mathematically sound treatment of the foundations of analytical mechanics, and of the relation of classical mechanics to relativity and quantum theory. A distinguishing feature is its integration of special relativity into the teaching of classical mechanics. After a thorough review of the traditional theory, Part II of the book introduces extended Lagrangian and Hamiltonian methods that treat time as a transformable coordinate rather than the fixed parameter of Newtonian physics. Advanced topics such as covariant Langrangians and Hamiltonians, canonical transformations, and Hamilton-Jacobi methods are simplified by the use of this extended theory. The definition of canonical transformation no longer excludes the Lorentz transformation of special relativity. This is also a book for those who study analytical mechanics to prepare for a critical exploration of quantum mechanics since comparisons to quantum mechanics appear throughout the text. The extended Hamiltonian theory with time as a coordinate is compared to Dirac's formalism of primary phase space constraints. The chapter on relativistic mechanics shows how to use covariant Hamiltonian theory to write the Klein-Gordon and Dirac equations. The chapter on Hamilton-Jacobi theory includes a discussion of the closely related Bohm hidden variable model of quantum mechanics. Classical mechanics itself is presented with an emphasis on methods such as linear vector operators and dyadics that will familiarise the student with similar techniques in quantum theory. Several of the current fundamental problems in theoretical physics require a rethinking of the quantum–classical connection.Less
This book provides an innovative and mathematically sound treatment of the foundations of analytical mechanics, and of the relation of classical mechanics to relativity and quantum theory. A distinguishing feature is its integration of special relativity into the teaching of classical mechanics. After a thorough review of the traditional theory, Part II of the book introduces extended Lagrangian and Hamiltonian methods that treat time as a transformable coordinate rather than the fixed parameter of Newtonian physics. Advanced topics such as covariant Langrangians and Hamiltonians, canonical transformations, and Hamilton-Jacobi methods are simplified by the use of this extended theory. The definition of canonical transformation no longer excludes the Lorentz transformation of special relativity. This is also a book for those who study analytical mechanics to prepare for a critical exploration of quantum mechanics since comparisons to quantum mechanics appear throughout the text. The extended Hamiltonian theory with time as a coordinate is compared to Dirac's formalism of primary phase space constraints. The chapter on relativistic mechanics shows how to use covariant Hamiltonian theory to write the Klein-Gordon and Dirac equations. The chapter on Hamilton-Jacobi theory includes a discussion of the closely related Bohm hidden variable model of quantum mechanics. Classical mechanics itself is presented with an emphasis on methods such as linear vector operators and dyadics that will familiarise the student with similar techniques in quantum theory. Several of the current fundamental problems in theoretical physics require a rethinking of the quantum–classical connection.
