Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring”, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, Pennsylvania, October 23–25, 2005, pages 637–646.

BibTeX

@InProceedings{Decomposition_FOCS2005,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Ken-ichi Kawarabayashi},
  TITLE         = {Algorithmic Graph Minor Theory: Decomposition,
                   Approximation, and Coloring},
  BOOKTITLE     = {Proceedings of the 46th Annual IEEE Symposium on Foundations
                   of Computer Science (FOCS 2005)},
  bookurl       = {http://www.cs.cornell.edu/Research/focs05/},
  ADDRESS       = {Pittsburgh, Pennsylvania},
  MONTH         = {October 23--25},
  YEAR          = 2005,
  PAGES         = {637--646},

  withstudent   = 1,
  length        = {10 pages},
  doi           = {https://dx.doi.org/10.1109/SFCS.2005.14},
  dblp          = {https://dblp.org/rec/conf/focs/DemaineHK05},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1109/SFCS.2005.14">IEEE</A>.},
}

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.

Comments:

This paper is also available from IEEE.

Length:

The paper is 10 pages.

Availability:

The paper is available in PostScript (314k), gzipped PostScript (110k), and PDF (177k).

See information on file formats.

[Google Scholar search]