A special case for subset interconnection designs

✍ Scribed by Du Ding-Zhu; Gao Biao; Wu Weili

• Book ID: 104294794
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 528 KB
• Volume: 78
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00023-1

✦ Synopsis

Given a set X and subsets Xl.. .X,,,, me consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1.. ,m, the subgraph G, induced by X, is connected. WC show that in the special cast that every point in X appears in at most three X,'s, the problem is still MAX SNP-complete: however. there exists a polynomialtime approximation within a factor of i from optimal. As an intermediate result. we also shou that the vertex cover problem in cubic graphs is MAX SNP-complete.