Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor”, in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2002), Lecture Notes in Computer Science, volume 2462, Rome, Italy, September 17–21, 2002, pages 67–80.
We give polynomial-time constant-factor approximation algorithms
for the treewidth and branchwidth of any H-minor-free graph
for a given graph H with crossing number at most 1.
The approximation factors are 1.5 for treewidth and 2.25 for branchwidth.
In particular, our result directly applies to classes of nonplanar graphs
such as K5-minor-free graphs and
Along the way, we present a polynomial-time algorithm to decompose
H-minor-free graphs into planar graphs and graphs of treewidth at most
cH (a constant dependent on H)
using clique sums.
This result has several applications in designing fully polynomial-time
approximation schemes and fixed-parameter algorithms for many
NP-complete problems on these graphs.
- The paper is \copyright Springer-Verlag.
- The paper is 14 pages.
- The paper is available in PostScript (213k) and PDF (169k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- CliqueSum_JCSS (Approximation algorithms for classes of graphs excluding single-crossing graphs as minors)
- CliqueSum_ISAAC2002 (Exponential Speedup of Fixed-Parameter Algorithms on K3,3-minor-free or K5-minor-free Graphs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 1, 2023 by