Invitation to Fixed-Parameter Algorithms [Niedermeier 2006-03-30].pdf

(1663 KB) Pobierz
Oxford Lecture Series in
Mathematics and its Applications 31
Series Editors
John Ball Dominic Welsh
OXFORD LECTURE SERIES
IN MATHEMATICS AND ITS APPLICATIONS
1. J. C. Baez (ed.):
Knots and quantum gravity
2. I. Fonseca and W. Gangbo:
Degree theory in analysis and applications
3. P. L. Lions:
Mathematical topics in fluid mechanics, Vol. 1: Incompressible
models
4. J. E. Beasley (ed.):
Advances in linear and integer programming
5. L. W. Beineke and R. J. Wilson (eds):
Graph connections: Relationships
between graph theory and other areas of mathematics
6. I. Anderson:
Combinatorial designs and tournaments
7. G. David and S. W. Semmes:
Fractured fractals and broken dreams
8. Oliver Pretzel:
Codes and algebraic curves
9. M. Karpinski and W. Rytter:
Fast parallel algorithms for graph matching
problems
10. P. L. Lions:
Mathematical topics in fluid mechanics, Vol. 2: Compressible
models
11. W. T. Tutte:
Graph theory as I have known it
12. Andrea Braides and Anneliese Defranceschi:
Homogenization of multiple
integrals
13. Thierry Cazenave and Alain Haraux:
An introduction to semilinear evolution
equations
14. J. Y. Chemin:
Perfect incompressible fluids
15. Giuseppe Buttazzo, Mariano Giaquinta and Stefan Hildebrandt:
One-dimensional variational problems: an introduction
16. Alexander I. Bobenko and Ruedi Seiler:
Discrete integrable geometry and
physics
17. Doina Cioranescu and Patrizia Donato:
An introduction to homogenization
18. E. J. Janse van Rensburg:
The statistical mechanics of interacting walks,
polygons, animals and vesicles
19. S. Kuksin:
Hamiltonian partial differential equations
20. Alberto Bressan:
Hyperbolic systems of conservation laws: the
one-dimensional Cauchy problem
21. B. Perthame:
Kinetic formulation of conservation laws
22. A. Braides:
Gamma-convergence for beginners
23. Robert Leese and Stephen Hurley:
Methods and algorithms for radio channel
assignment
24. Charles Semple and Mike Steel:
Phylogenetics
25. Luigi Ambrosio and Paolo Tilli:
Topics on Analysis in Metric Spaces
26. Eduard Feireisl:
Dynamics of Viscous Compressible Fluids
27. Antonín Novotn�½ and Ivan Straškraba:
Introduction to the Mathematical
Theory of Compressible Flow
28. Pavol Hell and Jarik Nesetril:
Graphs and Homomorphisms
29. Pavel Etingof and Frederic Latour:
The dynamical Yang-Baxter equation,
representation theory, and quantum integrable systems
30. Jorge Ramirez Alfonsin:
The Diophantine Frobenius Problem
31. Rolf Niedermeier:
Invitation to Fixed-Parameter Algorithms
Invitation to Fixed-Parameter
Algorithms
Rolf Niedermeier
Institut für Informatik, Friedrich-Schiller-Universität Jena
1
Great Clarendon Street, Oxford OX2 6DP
Oxford University Press is a department of the University of Oxford.
It furthers the University’s objective of excellence in research, scholarship,
and education by publishing worldwide in
Oxford New York
Auckland Cape Town Dar es Salaam Hong Kong Karachi
Kuala Lumpur Madrid Melbourne Mexico City Nairobi
New Delhi Shanghai Taipei Toronto
With offices in
Argentina Austria Brazil Chile Czech Republic France Greece
Guatemala Hungary Italy Japan Poland Portugal Singapore
South Korea Switzerland Thailand Turkey Ukraine Vietnam
Oxford is a registered trade mark of Oxford University Press
in the UK and in certain other countries
Published in the United States
by Oxford University Press Inc., New York
© Oxford University Press, 2006
The moral rights of the author have been asserted
Database right Oxford University Press (maker)
First published 2006
All rights reserved. No part of this publication may be reproduced,
stored in a retrieval system, or transmitted, in any form or by any means,
without the prior permission in writing of Oxford University Press,
or as expressly permitted by law, or under terms agreed with the appropriate
reprographics rights organization. Enquiries concerning reproduction
outside the scope of the above should be sent to the Rights Department,
Oxford University Press, at the address above
You must not circulate this book in any other binding or cover
and you must impose this same condition on any acquirer
British Library Cataloguing in Publication Data
Data available
Library of Congress Cataloging in Publication Data
Data available
A
Typeset by Author using L TEX
Printed in Great Britain
on acid-free paper by
Biddles Ltd, King’s Lynn, Norfolk
1
ISBN 0–19–856607–7
978–0–19–856607–6
1 3 5 7 9 10 8 6 4 2
PREFACE
This book grew out of my
habilitationsschrift
at the University of T¨bingen in
u
2002. Currently, there is only one monograph dealing with the issue of fixed-
parameter algorithms: Rod G. Downey and Michael R. Fellows’ groundbreaking
monograph
Parameterized Complexity
(1999). Since then there have been numer-
ous new results in this field of exactly solving combinatorially hard problems.
Moreover, Downey and Fellows’ monograph focuses more on structural com-
plexity theory issues than on concrete algorithm design and analysis. By way
of contrast, the objective of this book is to focus on the algorithmic side of
parameterized complexity, giving a fresh view of this highly innovative field of
algorithmic research.
The book is divided into three parts:
1. a broad introduction that provides the general philosophy and motivation;
2. a part on algorithmic methods developed over the years in fixed-parameter
algorithmics, forming the core of the book; and
3. a final section discussing the essentials of parameterized hardness theory,
focusing first 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 methodology presented.
The book is intended for advanced students in computer science and related
fields as well as people generally working with algorithms for discrete problems.
It has particular relevance when studying ways to cope with computational in-
tractability as expressed by
NP-hardness
theory.
The reader is recommended to start with Part I, but Parts II and III do
not need to be read in the given order. Thus, from Chapter 7 on (with a few
exceptions) there are almost no restrictions concerning the chosen order. The
material presented can be used to form a course exclusively dedicated to the
topic of fixed-parameter algorithms as well as to provide supplementary material
for an advanced algorithms class.
We believe that the concept of fixed-parameter tractability is fundamental
for the algorithmics of computationally hard discrete problems. Due to the ubiq-
uity of the proposed problem parameterization approach discussed here, fixed-
parameter algorithms should be seen as basic knowledge for every algorithm
designer. May this book help to spread this news.
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin