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
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
Last updated September 2, 2021 by