Given a complete weighted graph on vertex set X and subsets X-1,...,X-m of X, we consider the problem of finding a minimum total weight subgraph G such that for every i = 1,...,m, G contains a spanning tree for Xi. The NP-hardness of this problem was established in 1985 under Ronald V. Book's supervision. In this note, we present some results about its polynomial-time approximation. (C) 1998 Published by Elsevier Science B.V. AII rights reserved. [References: 13]
展开▼
