Skip to Main content Skip to Navigation
Book sections

Graph Minors and Parameterized Algorithm Design

Dimitrios M. Thilikos 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Book sections
Complete list of metadatas

Cited literature [119 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083542
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, November 17, 2014 - 2:17:55 PM
Last modification on : Tuesday, January 14, 2020 - 1:36:09 PM
Document(s) archivé(s) le : Friday, April 14, 2017 - 4:53:24 PM

File

minorsurvey.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Dimitrios M. Thilikos. Graph Minors and Parameterized Algorithm Design. The Multivariate Algorithmic Revolution and Beyond, LNCS (7370), pp.228-256, 2012, Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday - Part II, 978-3-642-30890-1. ⟨10.1007/978-3-642-30891-8_13⟩. ⟨lirmm-01083542⟩

Share

Metrics

Record views

190

Files downloads

488