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 K3,3-minor-free graphs. 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 BibTeX file.
Last updated June 13, 2024 by Erik Demaine.