Paper by Erik D. Demaine
- 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, PA, October 23–25, 2005, pages 637–646.
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.
- The paper is 10 pages.
- The paper is available in PostScript (314k), gzipped PostScript (110k), and PDF (177k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated October 17, 2021 by