On linear time minor tests with depth-first search

Research output: Contribution to journalArticleAcademicpeer-review

93 Citations (Scopus)

Abstract

Recent results on graph minors make it desirable to have efficient algorithms that, for a fixed set of graphs {H1,...,Hc}, test whether a given graph G contains at least one graph Hi as a minor. In this paper we show the following result: if at least one graph Hi, is a minor of a 2 ? k grid graph, and at least one graph Hi 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 ? {H1,..., Hc} 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! 2kn) time a cycle (or path) in a given graph with length ? k if it exists. ? 1993 Academic Press. All rights reserved.
Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalJournal of Algorithms
Volume14
Issue number1
DOIs
Publication statusPublished - Jan 1993
Externally publishedYes

Fingerprint Dive into the research topics of 'On linear time minor tests with depth-first search'. Together they form a unique fingerprint.

Cite this