Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors”, Algorithmica, volume 41, number 4, February 2005, pages 245–267.

BibTeX

@Article{CliqueSum_Algorithmica,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Dimitrios M. Thilikos},
  TITLE         = {Exponential Speedup of Fixed-Parameter Algorithms for
                   Classes of Graphs Excluding Single-Crossing Graphs as
                   Minors},
  JOURNAL       = {Algorithmica},
  journalurl    = {https://www.springer.com/journal/453},
  VOLUME        = 41,
  NUMBER        = 4,
  MONTH         = {February},
  YEAR          = 2005,
  PAGES         = {245--267},

  doi           = {https://dx.doi.org/10.1007/s00453-004-1125-y},
  dblp          = {https://dblp.org/rec/journals/algorithmica/DemaineHT05},
  COMMENTS      = {This paper is also available from <A HREF="https://doi.org/10.1007/s00453-004-1125-y">SpringerLink</A>.},
  PAPERS        = {CliqueSum_ISAAC2002},
  replaces      = {CliqueSum_ISAAC2002},
  withstudent   = 1,
}

Abstract:

We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in O(4^9.55 √k n^O(1)) time. Examples of such graph classes are the K_3,3-minor free graphs and the K₅-minor-free graphs. 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 collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PostScript (420k), gzipped PostScript (148k), 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)