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, PA, October 23–25, 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.
- 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]
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.