Abstract
A k-tree is a graph that can be reduced to the k-complete graph by sequentially removing k-degree vertices with completely connected neighbors. Partial k-trees are graphs embeddable in a k-tree with the same vertex set. In this paper we develop efficient algorithms for several path distance optimization problems on partial k-trees, and k-cable distance optimization problems on k-trees. Specifically, we develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a partial k-tree, we compute the diameter of a partial k-tree with equal edge lengths in linear time, and we construct an O(nk + 2) algorithm to solve the simple plant location problem in an n-vertex partial k-tree. Then, we analyze some cable distance optimization problems in k-trees. We derive some properties of cable distance in k-trees and we present a new characterization of a k-path in k-trees. Finally, we develop algorithms to solve a certain k-cable decomposition problem in k-trees in O(n2) time and to compute the k-cable diameter of a k-tree with equal edge lengths in linear time.