Approximations for subset interconnection designs

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 X i. 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.

Authors

• Xiufeng Du
• Weili Wu
• Dean F. Kelley

Keywords

• Subset interconnection
• Approximation
• Performance ratio