Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Exponential Speedup of Fixed Parameter Algorithms on K_3,3-minor-free or K₅-minor-free Graphs”, Technical Report MIT-LCS-TR-838, Massachusetts Institute of Technology, March 18, 2002.

BibTeX

@TechReport{CliqueSum_TR2002,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Dimitrios M. Thilikos},
  TITLE         = {Exponential Speedup of Fixed Parameter Algorithms on
                   $K_{3,3}$-minor-free or $K_5$-minor-free Graphs},
  INSTITUTION   = {Massachusetts Institute of Technology},
  NUMBER        = {MIT-LCS-TR-838},
  numberurl     = {http://www.lcs.mit.edu/publications/specpub.php?id=1611},
  MONTH         = {March 18},
  YEAR          = 2002,

  LENGTH        = {22 pages},
  PAPERS        = {CliqueSum_ISAAC2002; CliqueSum_APPROX2002}
}

Abstract:

We present a fixed parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of the K₅ or K_3,3 as a minor in time O(3^6 √34 k n^O(1)). In fact, we present our algorithm for any H-minor-free graph where H is a single-crossing graph (can be drawn on the plane with at most one crossing) and obtain the algorithm for K_3,3(K₅)-minor-free graphs as a special case. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set and a series of vertex removal problems. Our work generalizes and extends the recent result of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (non-planar) classes of graphs.

Length:

The paper is 22 pages.

Availability:

The paper is available in PostScript (318k), gzipped PostScript (119k), and PDF (251k).

See information on file formats.

[Google Scholar search]

Related papers:

CliqueSum_ISAAC2002 (Exponential Speedup of Fixed-Parameter Algorithms on K_3,3-minor-free or K₅-minor-free Graphs)

CliqueSum_APPROX2002 (1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor)