Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar, “Approximation Algorithms via Contraction Decomposition”, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 278–287.
- Abstract:
-
We prove that the edges of every graph of bounded (Euler)
genus can be partitioned into any prescribed
number k of pieces such that contracting any piece
results in a graph of bounded treewidth
(where the bound depends on k).
This decomposition result parallels an analogous, simpler result for
edge deletions instead of contractions, obtained in
[Bak94, Epp00, DDO+04, DHK05],
and it generalizes a similar result for “compression”
(a variant of contraction) in planar graphs [Kle05].
Our decomposition result is a powerful tool for obtaining PTASs for
contraction-closed problems (whose optimal solution only improves under
contraction), a much more general class than minor-closed problems.
We prove that any contraction-closed problem satisfying just a few simple
conditions has a PTAS in bounded-genus graphs.
In particular, our framework yields PTASs for the weighted
Traveling Salesman Problem and for minimum-weight c-edge-connected
submultigraph on bounded-genus graphs, improving and generalizing
previous algorithms of [GKP95, AGK+98, Kle05, Gri00, CGSZ04, BCGZ05].
We also highlight the only main difficulty in extending our results to
general H-minor-free graphs.
- Availability:
- The paper is available in PostScript (507k), gzipped PostScript (212k), and PDF (264k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ContractionTSP_Combinatorica (Approximation Algorithms via Contraction Decomposition)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.