OUP: UK General Catalogue

NEVER MISS AN OXFORD SALE (SIGN UP HERE) |

VIEW BASKET

UK and Europe

Book Catalogue

	Help with online ordering
	How to order
	Postage
	Returns policy
	Search the catalogue
	VAT rates

	Authors
	Description
	Reviews
	Table of Contents

Invitation to Fixed Parameter Algorithms

Rolf Niedermeier

Price: £67.00 (hardback)
ISBN-13: 978-0-19-856607-6
Publication date: 2 February 2006
312 pages, 25 line illus., 234x156 mm
Series: Oxford Lecture Series in Mathematics and Its Applications number No. 31
Search for titles in the same series

A sample of this book is available in PDF format

Comment on this title

Ordering

Individual customers may:
order by phone, post, or fax.
Manufactured on Demand - stock will be supplied on a firm sale basis within 28 days

Teachers in UK and European schools (and FE colleges in the UK):

order by phone, post, or fax

This book is available in Oxford Scholarship Online

Reviews

'This book is an excellent introduction to the algorithmic aspects of the field' - William Gasarch and Kin Keung Ma, The Computer Journal, Vol. 51 No. 1
'Niedermeier presents a wider range of concrete problems and pronlem variants, highlighting many algorithmic tricks and applications.' - Daniel Marx, Mathematical Review

Description

Covers the most recent ideas and concepts in the developing area of fixed-parameter algorithms
Growing and highly topical area
Numerous real-life case studies
Aimed at graduate and research mathematicians, programmers, algorithm designers, and computer scientists

This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for optimally solving computationally hard combinatorial problems.

The book 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 from 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.

Aimed at graduate and research mathematicians, programmers, algorithm designers, and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research.

Readership: Graduate and research mathematicians, computer scientists and computational biologists.

Contents

Part I: Foundations

1. Introduction to Fixed-Parameter Algorithms

2. Preliminaries and Agreements

3. Parameterized Complexity Theory - A Primer

4. Vertex Cover - An Illustrative Example

5. The Art of Problem Parameterization

6. Summary and Concluding Remarks

Part II: Algorithmic Methods

7. Data Reduction and Problem Kernels

8. Depth-Bounded Search Trees

9. Dynamic Programming

10. Tree Decompositions of Graphs

11. Further Advanced Techniques

12. Summary and Concluding Remarks

Part III: Some Theory, Some Case Studies

13. Parameterized Complexity Theory

14. Connections to Approximation Algorithms

15. Selected Case Studies

16. Zukunftsmusik

References

Index

Authors, editors, and contributors

Rolf Niedermeier, Universitaet Jena

Links to web resources and related information

More in the same subject area:
Combinatorics & graph theory

The specification in this catalogue, including without limitation price, format, extent, number of illustrations, and month of publication, was as accurate as possible at the time the catalogue was compiled. Occasionally, due to the nature of some contractual restrictions, we are unable to ship a specific product to a particular territory. Jacket images are provisional and liable to change before publication.