Parameterized Algorithms [Cygan et al. 2015-09-14].pdf

(8072 KB) Pobierz
Marek Cygan · Fedor V. Fomin
Łukasz Kowalik · Daniel Lokshtanov
Dániel Marx · Marcin Pilipczuk
Michał Pilipczuk · Saket Saurabh
Parameterized
Algorithms
Parameterized Algorithms
Marek Cygan Fedor V. Fomin
Łukasz
Kowalik Daniel Lokshtanov
Dániel Marx Marcin Pilipczuk
Michał Pilipczuk Saket Saurabh
•
•
•
•
Parameterized Algorithms
123
Marek Cygan
Institute of Informatics
University of Warsaw
Warsaw
Poland
Fedor V. Fomin
Department of Informatics
University of Bergen
Bergen
Norway
Łukasz
Kowalik
Institute of Informatics
University of Warsaw
Warsaw
Poland
Daniel Lokshtanov
Department of Informatics
University of Bergen
Bergen
Norway
Dániel Marx
Institute for Computer Science and Control
Hungarian Academy of Sciences
Budapest
Hungary
Marcin Pilipczuk
Institute of Informatics
University of Warsaw
Warsaw
Poland
Michał Pilipczuk
Institute of Informatics
University of Warsaw
Warsaw
Poland
Saket Saurabh
C.I.T. Campus
The Institute of Mathematical Sciences
Chennai
India
ISBN 978-3-319-21274-6
DOI 10.1007/978-3-319-21275-3
ISBN 978-3-319-21275-3
(eBook)
Library of Congress Control Number: 2015946081
Springer Cham Heidelberg New York Dordrecht London
©
Springer International Publishing Switzerland 2015
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part
of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission
or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this
publication does not imply, even in the absence of a specific statement, that such names are exempt from
the relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this
book are believed to be true and accurate at the date of publication. Neither the publisher nor the
authors or the editors give a warranty, express or implied, with respect to the material contained herein or
for any errors or omissions that may have been made.
Printed on acid-free paper
Springer International Publishing AG Switzerland is part of Springer Science+Business Media
(www.springer.com)
Preface
The goal of this textbook is twofold. First, the book serves as an introduction
to the field of parameterized algorithms and complexity accessible to graduate
students and advanced undergraduate students. Second, it contains a clean
and coherent account of some of the most recent tools and techniques in the
area.
Parameterized algorithmics analyzes running time in finer detail than clas-
sical complexity theory: instead of expressing the running time as a function
of the input size only, dependence on one or more parameters of the input in-
stance is taken into account. While there were examples of nontrivial param-
eterized algorithms in the literature, such as Lenstra’s algorithm for integer
linear programming [319] or the disjoint paths algorithm of Robertson and
Seymour [402], it was only in the late 1980s that Downey and Fellows [149],
building on joint work with Langston [180, 182, 183], proposed the system-
atic exploration of parameterized algorithms. Downey and Fellows laid the
foundations of a fruitful and deep theory, suitable for reasoning about the
complexity of parameterized algorithms. Their early work demonstrated that
fixed-parameter tractability is a ubiquitous phenomenon, naturally arising
in various contexts and applications. The parameterized view on algorithms
has led to a theory that is both mathematically beautiful and practically ap-
plicable. During the 30 years of its existence, the area has transformed into
a mainstream topic of theoretical computer science. A great number of new
results have been achieved, a wide array of techniques have been created,
and several open problems have been solved. At the time of writing, Google
Scholar gives more than 4000 papers containing the term “fixed-parameter
tractable”. While a full overview of the field in a single volume is no longer
possible, our goal is to present a selection of topics at the core of the field,
providing a key for understanding the developments in the area.
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin