Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs”, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 329–344.
We prove two structural decomposition theorems about graphs excluding a fixed
odd minor H, and show how these theorems can be used to obtain
approximation algorithms for several algorithmic problems in such graphs. Our
decomposition results provide new structural insights into
odd-H-minor-free graphs, on the one hand generalizing the central
structural result from Graph Minor Theory, and on the other hand providing an
algorithmic decomposition into two bounded-treewidth graphs, generalizing a
similar result for minors. As one example of how these structural results
conquer difficult problems, we obtain a polynomial-time 2-approximation for
vertex coloring in odd-H-minor-free graphs, improving on the previous
O(|V(H)|)-approximation for such graphs and generalizing
the previous 2-approximation for H-minor-free graphs. The class of
odd-H-minor-free graphs is a vast generalization of the well-studied
H-minor-free graph families and includes, for example, all bipartite
graphs plus a bounded number of apices. Odd-H-minor-free graphs are
particularly interesting from a structural graph theory perspective because
they break away from the sparsity of H-minor-free graphs, permitting a
quadratic number of edges.
- The paper is available in PostScript (405k), gzipped PostScript (141k), and PDF (288k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by