
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A 7/3Approximation for the Minimum Weight 3Connected Spanning Subgraph Problem
Hiroshi NAGAMOCHI Katsuhiro SEKI Toshihide IBARAKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.4
pp.687691 Publication Date: 2000/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: undirected graph, vertexconnectivity, approximation algorithm, spanning subgraph,
Full Text: PDF>>
Summary:
We consider the problem of finding a minimum weight kconnected spanning subgraph of a given edgeweighted graph G for k=3. The problem is known to be NPhard for k 2, and there are an O(n^{2}m) time 3approximation algorithm due to Nutov and Penn and an O(n^{8}) time 2approximation algorithm due to Dinitz and Nutov, where n and m are the numbers of vertices and edges in G, respectively. In this paper, we present a 7/3approximation algorithm which runs in O(n^{2}m) time.

