Name
Abstract | ||
|---|---|---|
In this paper, we consider the problem of constructing the shortest two-connected Steiner network on the Euclidean plane. For a given set P of points on the Euclidean plane, let I,(P) denote the length of the shortest two-connected Steiner network on P divided by the length of the shortest two-connected spanning network on P. We prove that I-2(P) = 1, if any one of the following conditions is satisfied: (1) All points in P are on the sides of the convex hull of P; (2) all points except one in P are on the sides of the convex hull of P; or (3) the cardinality of P is no greater than 5. Moreover, we obtain general lower and upper bounds for I-2(P) as follows: (root 3/2) less than or equal to inf{I-2(P) \ P} less than or equal to 2[(root 3 + 2)/(root 3 + 6)]. We also show that Christofides' heuristic for the traveling salesman problem can be used to design a polynomial-time algorithm for finding the shortest two-connected Steiner and spanning network with guaranteed worst-case performance ratio of root 3 and 3/2, respectively. (C) 1998 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1002/(SICI)1097-0037(199809)32:2<133::AID-NET6>3.0.CO;2-C | NETWORKS |
Keywords | Field | DocType |
euclidean distance | Combinatorics,Shortest path problem,Steiner tree problem,Euclidean distance,Convex hull,Travelling salesman problem,Spanning tree,Time complexity,Mathematics,Euclidean shortest path | Journal |
Volume | Issue | ISSN |
32 | 2 | 0028-3045 |
Citations | PageRank | References |
10 | 1.14 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| D. Frank Hsu | 1 | 722 | 66.32 |
| Xiao-dong Hu | 2 | 10 | 1.14 |