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”, Technical Report MIT-LCS-TR-838, Massachusetts Institute of Technology, March 18, 2002.
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(36 √34 k nO(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
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.
- The paper is 22 pages.
- 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 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 July 21, 2021 by