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.
Type de document :
Chapitre d'ouvrage
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〉
Liste complète des métadonnées

Littérature citée [119 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083542
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 14:17:55
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 14 avril 2017 - 16:53:24

Fichier

minorsurvey.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

146