**Reference**:- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Exponential Speedup of Fixed-Parameter Algorithms on
*K*_{3,3}-minor-free or*K*_{5}-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. **Abstract**:-
We present a fixed-parameter algorithm that constructively solves the
*k*-dominating set problem on graphs excluding one of the*K*_{5}or*K*_{3,3}as a minor in time*O*(4^{16.5 √k}*n*^{O(1)}), which is an exponential factor faster than the previous*O*(2^{O(k)}n^{O(1)}). 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*K*_{3,3}(*K*_{5})-minor-free 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. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Length**:- The paper is 12 pages.
**Availability**:- 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
*K*_{3,3}-minor-free or*K*_{5}-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.

Last updated May 16, 2024 by Erik Demaine.