Paper by Erik D. Demaine

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.

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(49.55 √k nO(1)) time. Examples of such graph classes are the K3,3-minor free graphs and the K5-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.

This paper is also available from SpringerLink.

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 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 July 25, 2017 by Erik Demaine.