Name
Abstract | ||
|---|---|---|
We give quasipolynomial-time approximation algorithms for designing networks with minimum degree. Using our methods, one can design one-connected networks to meet a variety of connectivity requirements. The degree of the output network is guaranteed to be at most (1+ε) times optimal, plus an additive error of O(log n/ε) for any εs0. We also provide a quasipolynomial-time approximation algorithm for designing a two-edge-connected spanning subgraph of a given two-edge-connected graph of approximately minimum degree. The performance guarantee is identical to that for one-connected networks. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/3-540-56287-7_112 | FSTTCS |
Keywords | Field | DocType |
small degree,designing networks,local optimality,connected graph,optimal design | Binary logarithm,Discrete mathematics,Graph,Approximation algorithm,Spanning subgraph,Combinatorics,Computer science,Steiner tree problem,Performance guarantee | Conference |
Volume | ISSN | ISBN |
652 | 0302-9743 | 3-540-56287-7 |
Citations | PageRank | References |
12 | 1.48 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Ravi | 1 | 2898 | 275.40 |
| Balaji Raghavachari | 2 | 1001 | 77.77 |
| Philip N. Klein | 3 | 2681 | 256.19 |