Graph minors and parameterized algorithm design

Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingChapter


The Graph Minors Theory, developed by Robertson and Seymour, has been one of the most influential mathematical theories in parameterized 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 applications of core theorems such as the grid-exclusion theorem, and we give a brief description of the irrelevant vertex technique.

Original languageEnglish (US)
Title of host publicationThe Multivariate Algorithmic Revolution and Beyond
Subtitle of host publicationEssays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday
EditorsBodlaender Hans, Downey Rod, Fomin Fedor, Marx Daniel
Number of pages29
StatePublished - 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • bidimensionality
  • graph minors
  • irrelevant vertex technique
  • linkages
  • parameterized algorithms
  • treewidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Graph minors and parameterized algorithm design'. Together they form a unique fingerprint.

Cite this