Name
Abstract | ||
|---|---|---|
We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connec-tivity is specified by "proper" functions, a class of 0-1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial-time approxima-tion algorithms for finding two-edge-connected span-ning subgraphs of approximately minimum degree of a given two-edge-connected graph, and a spanning tree (branching) of approximately minimum degree of a di-rected graph. The degree of the output network in all cases is guaranteed to be at most (1 ) times the optimal degree, plus an additive O(log<SUB>1 n) for any > 0.Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well esti-mated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. ? 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 203-215 2004 |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1002/net.20031 | Networks |
Keywords | DocType | Volume |
graph connectivity,spanning tree,branch and bound,connected graph,approximation algorithms,np hard problem,np hard problems,network design,linear program | Journal | 44 |
Issue | ISSN | Citations |
3 | 0028-3045 | 14 |
PageRank | References | Authors |
0.77 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philip N. Klein | 1 | 2681 | 256.19 |
| Radha Krishnan | 2 | 30 | 3.30 |
| Balaji Raghavachari | 3 | 1001 | 77.77 |
| R. Ravi | 4 | 2898 | 275.40 |