Skip to main content
SpringerLink
Log in
Book cover

The Multivariate Algorithmic Revolution and Beyond

Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday

  • Book
  • © 2012

Overview

Editors:
  1. Hans L. Bodlaender

    1. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rod Downey

    1. School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Fedor V. Fomin

    1. Institute of Informatics, University of Bergen, Bergen, Norway

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Dániel Marx

    1. Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Features classical research papers reflecting the breadth of the work and influence of Michael R. Fellows
  • Commemorative publication
  • Written by experts

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 7370)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (20 chapters)

  1. Front Matter

    Download chapter PDF

  3. Surveys

    1. Front Matter

      Pages 89-89
      Download chapter PDF

    2. A Basic Parameterized Complexity Primer

      • Rod Downey
      Pages 91-128

    3. Kernelization – Preprocessing with a Guarantee

      • Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh
      Pages 129-161

    4. Parameterized Complexity and Subexponential-Time Computability

      • Jianer Chen, Iyad A. Kanj
      Pages 162-195

    5. Fixed-Parameter Tractability of Treewidth and Pathwidth

      • Hans L. Bodlaender
      Pages 196-227

    6. Graph Minors and Parameterized Algorithm Design

      • Dimitrios M. Thilikos
      Pages 228-256

    7. Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey

      • Gregory Gutin, Anders Yeo
      Pages 257-286

    8. Backdoors to Satisfaction

      • Serge Gaspers, Stefan Szeider
      Pages 287-317

    9. Studies in Computational Aspects of Voting

      • Nadja Betzler, Robert Bredereck, Jiehua Chen, Rolf Niedermeier
      Pages 318-363

    10. A Parameterized Halting Problem

      • Yijia Chen, Jörg Flum
      Pages 364-397
Back to top

Keywords

About this book

Parameterized complexity is currently a thriving field in complexity theory and algorithm design. A significant part of the success of the field can be attributed to Michael R. Fellows.
This Festschrift has been published in honor of Mike Fellows on the occasion of his 60th birthday. It contains 20 papers that showcase the important scientific contributions of this remarkable man, describes the history of the field of parameterized complexity, and also reflects on other parts of Mike Fellows’s unique and broad range of interests, including his work on the popularization of discrete mathematics for young children.
The volume contains several surveys that introduce the reader to the field of parameterized complexity and discuss important notions, results, and developments in this field.

Editors and Affiliations

  • Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

    Hans L. Bodlaender

  • School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand

    Rod Downey

  • Institute of Informatics, University of Bergen, Bergen, Norway

    Fedor V. Fomin

  • Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary

    Dániel Marx

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation