Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Exponential Speedup of Fixed-Parameter Algorithms on K3,3-minor-free or K5-minor-free Graphs”, in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, volume 2518, Vancouver, British Columbia, Canada, November 20–23, 2002, pages 262–273.
We present a fixed-parameter algorithm that constructively solves the
k-dominating set problem on graphs excluding one of the
K5 or K3,3 as a minor in time
O(416.5 √k nO(1)),
which is an exponential factor faster than the previous
In fact, we present our algorithm for any H-minor-free graph where
H is a single-crossing graph (can be drawn in the plane with at most one
crossing) and obtain the algorithm for
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 by Alber et al. to other (non-planar) classes of graphs.
- This paper is also available from SpringerLink.
- The paper is \copyright Springer-Verlag.
- The paper is 12 pages.
- The paper is available in PostScript (200k), gzipped PostScript (78k), and PDF (225k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- CliqueSum_Algorithmica (Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors)
- CliqueSum_TR2002 (Exponential Speedup of Fixed Parameter Algorithms on K3,3-minor-free or K5-minor-free Graphs)
- CliqueSum_APPROX2002 (1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 27, 2015 by