Name
Abstract | ||
|---|---|---|
We consider a basic problem in the design of reliable networks, namely, that of finding a minimum-weight 2-connected subgraph spanning a given set K of vertices in a planar graph. We show a relationship between this problem and that of finding shortest trails and cycles enclosing K, and derive a polynomial-time algorithm in the case when the vertices of K all lie on the same face. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0167-6377(96)00046-6 | Oper. Res. Lett. |
Keywords | Field | DocType |
steiner tree,planar graph,network survivability,reliable network,basic problem,2-connected subgraph,two-connected,two-connected subgraphs,polynomial-time algorithm | Graph theory,Discrete mathematics,Combinatorics,Vertex (geometry),Steiner tree problem,Network survivability,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 2 | Operations Research Letters |
Citations | PageRank | References |
2 | 0.40 | 9 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Scott Provan | 1 | 678 | 90.11 |