Skip to main content
SpringerLink
Log in

Treewidth, Kernels, and Algorithms

Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday

  • Book
  • © 2020

Overview

Editors:
  1. Fedor V. Fomin

    1. University of Bergen, Bergen, Norway

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Stefan Kratsch

    1. Humboldt-University, Berlin, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Erik Jan van Leeuwen

    1. Utrecht University, Utrecht, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Contains refereed papers dedicated to Hans L. Bodlaender and to his work
  • Collects a number of papers by Hans' collaborators over the years presenting a broad range of topics reflecting Hans’ versatility
  • Depicts Hans L. Bodlaender’s major contributions to algorithms research, complexity theory, and graph theory

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

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 54.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 69.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 (19 chapters)

  1. Front Matter

    Pages i-lv
    Download chapter PDF

  2. Short Contributions

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Seeing Arboretum for the (partial k-) Trees

      • Stefan Arnborg, Andrzej Proskurowski
      Pages 3-6

    3. Collaborating with Hans: Some Remaining Wonderments

      • Michael R. Fellows, Frances A. Rosamond
      Pages 7-17

    4. Hans Bodlaender and the Theory of Kernelization Lower Bounds

      • Danny Hermelin
      Pages 18-21

    5. Algorithms, Complexity, and Hans

      • Jan van Leeuwen
      Pages 22-27

  3. Surveys

    1. Front Matter

      Pages 29-29
      Download chapter PDF

    2. Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs

      • Mark de Berg, Sándor Kisfaludi-Bak
      Pages 31-48

    3. As Time Goes By: Reflections on Treewidth for Temporal Graphs

      • Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, Philipp Zschoche
      Pages 49-77

    4. Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs

      • Alexander Grigoriev
      Pages 78-88

    5. Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds

      • Bart M. P. Jansen
      Pages 89-111Open Access

    6. Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths

      • Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
      Pages 112-128

    7. Four Shorts Stories on Surprising Algorithmic Uses of Treewidth

      • Dániel Marx
      Pages 129-144

    8. Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

      • Jesper Nederlof
      Pages 145-164

    9. A Survey on Spanning Tree Congestion

      • Yota Otachi
      Pages 165-172

    10. Surprising Applications of Treewidth Bounds for Planar Graphs

      • Marcin Pilipczuk
      Pages 173-188

    11. Computing Tree Decompositions

      • Michał Pilipczuk
      Pages 189-213

    12. Experimental Analysis of Treewidth

      • Hisao Tamaki
      Pages 214-221

    13. A Retrospective on (Meta) Kernelization

      • Dimitrios M. Thilikos
      Pages 222-246

    14. Games, Puzzles and Treewidth

      • Tom C. van der Zanden
      Pages 247-261
Back to top

Keywords

About this book

This Festschrift was published in honor of Hans L. Bodlaender on the occasion of his 60th birthday. 

The 14 full and 5 short contributions included in this volume show the many transformative discoveries made by H.L. Bodlaender in the areas of graph algorithms, parameterized complexity, kernelization and combinatorial games. The papers are written by his former Ph.D. students and colleagues as well as by his former Ph.D. advisor, Jan van Leeuwen.

Chapter “Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds” is available open access under a Creative Commons Attribution 4.0 International License via link.springer.com.

Editors and Affiliations

  • University of Bergen, Bergen, Norway

    Fedor V. Fomin

  • Humboldt-University, Berlin, Germany

    Stefan Kratsch

  • Utrecht University, Utrecht, The Netherlands

    Erik Jan van Leeuwen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation