Treewidth, Kernels, and Algorithms

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

AvFedor V. Fomin,Stefan Kratsch

Häftad, Engelska, 2020

Del 12160 i serien Lecture Notes in Computer Science

715 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Beskrivning

This Festschrift was published in honor of Hans L. 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.

Produktinformation

Utgivningsdatum:2020-03-17
Mått:155 x 235 x 23 mm
Vikt:536 g
Format:Häftad
Språk:Engelska
Serie:Lecture Notes in Computer Science
Antal sidor:299
Förlag:Springer Nature Switzerland AG
ISBN:9783030420703

Utforska kategorier

Innehållsförteckning

Seeing Arboretum for the (partial k) Trees.- Collaborating With Hans: Some Remaining Wonderments.- Hans Bodlaender and the Theory of Kernelization Lower Bounds.- Algorithms, Complexity, and Hans.- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs.- As Time Goes By: Reflections on Treewidth for Temporal Graphs.- Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs.- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds.- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths.- Four shorts stories on surprising algorithmic uses of treewidth.- Algorithms for NP-Hard Problems via Rank-related Parameters of Matrices.- A Survey on Spanning Tree Congestion.- Surprising Applications of Treewidth Bounds for Planar Graphs.- Computing tree decompositions.- Experimental analysis of treewidth.- A Retrospective on (Meta) Kernelization.- Games, Puzzles and Treewidth.- Fast Algorithms for Join Operations on Tree Decompositions.