@conference {14563,
title = {Algorithmic graph minor theory: Decomposition, approximation, and coloring},
booktitle = {Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on},
year = {2005},
month = {2005///},
pages = {637 - 646},
abstract = {At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.},
keywords = {algorithmic graph minor theory, approximation algorithm, combinatorial polylogarithmic approximation, computational complexity, constant-factor approximation, graph algorithm, graph coloring, graph colouring, half-integral multicommodity flow, largest grid minor, maximization problem, minimization problem, polynomial-time algorithm, subexponential fixed-parameter algorithm, topological graph theory, treewidth},
doi = {10.1109/SFCS.2005.14},
author = {Demaine,E. D and Hajiaghayi, Mohammad T. and Kawarabayashi,K.}
}