## Abstract

Recent results on graph minors make it desirable to have efficient algorithms that, for a fixed set of graphs {H_{1},...,H_{c}}, test whether a given graph G contains at least one graph H_{i} as a minor. In this paper we show the following result: if at least one graph H_{i}, is a minor of a 2 × k grid graph, and at least one graph H_{i} is a minor of a circus graph, then one can test in O(n) time whether a given graph G contains at least one graph H ∈ {H_{1},..., H_{c}} as a minor. This result generalizes a result of Fellows and Langston. The algorithm is based on depth-first search and on dynamic programming on graphs with bounded treewidth. As a corollary, it follows that the MAXIMUM LEAF SPANNING TREE problem can be solved in linear time for fixed k. We also discuss that, with small modifications, an algorithm of Fellows and Langston can be modified to an algorithm that finds in O(k! 2^{k}n) time a cycle (or path) in a given graph with length ≥ k if it exists.

Original language | English |
---|---|

Pages (from-to) | 1-23 |

Number of pages | 23 |

Journal | Journal of Algorithms |

Volume | 14 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Jan 1993 |