## Abstract

We present a fixed-parameter algorithm that constructively solves the k-dominating set problem on graphs excluding one of 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 (nonplanar) classes of graphs.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings |

Pages | 262-273 |

Number of pages | 12 |

DOIs | |

State | Published - 2002 |

Event | 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: Nov 21 2002 → Nov 23 2002 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2518 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 |
---|---|

Country/Territory | Canada |

City | Vancouver, BC |

Period | 11/21/02 → 11/23/02 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science

## Fingerprint

Dive into the research topics of 'Exponential speedup of fixed-parameter algorithms on K_{3}

_{3}-minor-free or K

_{5}-minor-free graphs'. Together they form a unique fingerprint.