Abstract:
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.
