Searching for Spanning k-Caterpillars and k-Trees
Michael J. Dinneen, Masoud Khosravani · ResearchSpace (University of Auckland) · 2008
We consider the problems of finding spanning k-caterpillars and k-trees in graphs. We first show that the problem of whether a graph has a spanning k- caterpillar is NP-complete, for all k ≥ 1. Then we give a linear time algorithm for finding a spanning 1-caterpillar in a graph with treewidth k. Also, as a generalized versions of the depth-first search and the breadth-first search algorithms, we introduce the k-tree search (KTS) algorithm and we use it in a heuristic algorithm for finding a large k-caterpillar in a graph.