Logo image
Sign in
Graph Minors and Parameterized Algorithm Design
Book chapter   Open access

Graph Minors and Parameterized Algorithm Design

Dimitrios M. Thilikos
The Multivariate Algorithmic Revolution and Beyond, Vol.LNCS(7370), pp.228-256
Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday - Part II
2012

Abstract

graph minors parameterized algorithms treewidth bidimensional-ity irrelevant vertex technique linkages
The Graph Minors Theory, developed by Robertson and Sey-mour, has been one of the most influential mathematical theories in pa-rameterized algorithm design. We present some of the basic algorithmic techniques and methods that emerged from this theory. We discuss its direct meta-algorithmic consequences, we present the algorithmic appli-cations of core theorems such as the grid-exclusion theorem, and we give a brief description of the irrelevant vertex technique.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image