APPROXIMATIONS FOR SUBSET INTERCONNECTION DESIGNS

Authors
DUA XF WU WL KELLEY DF
Citation
Xf. Dua et al., APPROXIMATIONS FOR SUBSET INTERCONNECTION DESIGNS, Theoretical computer science, 207(1), 1998, pp. 171-180
Citations number
13
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
207
Issue
1
Year of publication
1998
Pages
171 - 180
Database
ISI
SICI code
0304-3975(1998)207:1<171:AFSID>2.0.ZU;2-0
Abstract
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 subg raph 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 Ron ald V. Book's supervision. In this note, we present some results about its polynomial-time approximation. (C) 1998 Published by Elsevier Sci ence B.V. AII rights reserved.