Faster approximation algorithms for weighted triconnectivity augmentation problems

Faster approximation algorithms for weighted triconnectivity augmentation problems

0.00 Avg rating0 Votes
Article ID: iaor2002902
Country: Netherlands
Volume: 21
Issue: 5
Start Page Number: 219
End Page Number: 223
Publication Date: Dec 1997
Journal: Operations Research Letters
Authors: ,
Abstract:

The problem of finding a minimum-weight augmenting edge-set to make a graph 3-vertex connected is considered. This problem is known to be NP-complete. We present a new 3-approximation algorithm for making an arbitrary graph 3-vertex connected. Our algorithm is simpler and faster than the previously known 3-approximation algorithm by a factor of O(n2), where n is the number of vertices of the graph. We also consider the problem of increasing the vertex-connectivity of a 2-connected graph from 2 to 3.

Reviews

Required fields are marked *. Your email address will not be published.