A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem

Hiroshi NAGAMOCHI  Katsuhiro SEKI  Toshihide IBARAKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.4   pp.687-691
Publication Date: 2000/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
undirected graph,  vertex-connectivity,  approximation algorithm,  spanning subgraph,  

Full Text: PDF(392.2KB)>>
Buy this Article




Summary: 
We consider the problem of finding a minimum weight k-connected spanning subgraph of a given edge-weighted graph G for k=3. The problem is known to be NP-hard for k 2, and there are an O(n2m) time 3-approximation algorithm due to Nutov and Penn and an O(n8) time 2-approximation 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/3-approximation algorithm which runs in O(n2m) time.