Name
Abstract | ||
|---|---|---|
The minimum cardinality 3-edge-connected spanning subgraph problem is considered. An approximation algorithm with a performance ratio of 4/3 ≈ 1.33 is presented. This improves the previous best ratio of 3/2 for the problem. The algorithm also works on multigraphs and guarantees the same approximation ratio. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73951-7_5 | WADS |
Keywords | Field | DocType |
minimum 3-edge-connectivity,approximation ratio,3-approximation algorithm,subgraph problem,approximation algorithm,performance ratio,minimum cardinality,previous best ratio,connectivity,combinatorial optimization,approximation algorithms | Approximation algorithm,Discrete mathematics,Combinatorics,Performance ratio,Minimax approximation algorithm,Cardinality,Combinatorial optimization,Christofides algorithm,Minimum k-cut,Mathematics,Reverse-delete algorithm | Conference |
Volume | ISSN | ISBN |
4619 | 0302-9743 | 3-540-73948-3 |
Citations | PageRank | References |
1 | 0.39 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prabhakar Gubbala | 1 | 5 | 1.17 |
| Balaji Raghavachari | 2 | 1001 | 77.77 |