Graph Minors and Parameterized Algorithm Design - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Book Sections Year : 2012

Graph Minors and Parameterized Algorithm Design

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.
Fichier principal
Vignette du fichier
minorsurvey.pdf (1 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01083542 , version 1 (17-11-2014)

Identifiers

Cite

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⟩
145 View
360 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More