Name
Abstract | ||
|---|---|---|
The problem of finding minimum weight spanning subgraphs with a given connectivityrequirement is considered. The problem is NP-hard when the connectivity requirementis greater than one. Polynomial time approximation algorithms for various weighted andunweighted connectivity problems are given.The following results are presented:1. For the unweighted k-edge-connectivity problem an approximation algorithm thatachieves a performance ratio of 1.85 is described. This is the first... |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1006/jagm.1996.0052 | Journal of Algorithms |
Keywords | Field | DocType |
satisfiability,triangle inequality | Approximation algorithm,Combinatorics,Computer science,Minimum weight,Technical report,Polynomial time approximation algorithm | Journal |
Volume | Issue | ISSN |
21 | 2 | 0196-6774 |
ISBN | Citations | PageRank |
0-89791-718-9 | 79 | 5.69 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Khuller | 1 | 4053 | 368.49 |
| Balaji Raghavachari | 2 | 1001 | 77.77 |