Paper Info
Title
A 5/4-approximation algorithm for minimum 2-edge-connectivity
Abstract
A 5/4-approximation algorithm is presented for the minimum cardinality 2-edge-connected spanning subgraph problem in undirected graphs. This improves the previous best approximation ratio of 4/3. It is shown that our ratio is tight with respect to current lower bounds, and any further improvement is possible only if new lower bounds are discovered.
Year
DOI
Venue
2003
10.5555/644108.644227
SODA
Keywords
Field
DocType
current lower bound,subgraph problem,undirected graph,4-approximation algorithm,previous best approximation ratio,new lower bound,minimum 2-edge-connectivity,minimum cardinality,lower bound,ad hoc networks,distributed algorithms
Discrete mathematics,Graph,Approximation algorithm,Combinatorics,Spanning subgraph,Computer science,Cardinality,Distributed algorithm,Connected dominating set,If and only if,Wireless ad hoc network
Conference
ISBN
Citations 
PageRank 
0-89871-538-5
24
1.18
References 
Authors
13
3
Name
Order
Citations
PageRank
Raja Jothi126413.98
Balaji Raghavachari2100177.77
Subramanian Varadarajan3241.18