Name
Abstract | ||
|---|---|---|
Given a set of fixed points, a set of moving points in the Euclidean plane, and a set of edges connecting these points, the problem we consider is that of locating the moving points so as to minimize the total length of edges, where zero-length edges are allowed. We study the special case where each point has degree at most three and show that it is related to the well-studied Steiner minimal tree problem. We prove that if a Steiner tree (a tree such that no two edges meet at an angle less than 120°) exists with the given topology, then it is the shortest network. We also propose an O(n2) time algorithm, where n is the number of fixed points, for obtaining the Steiner tree. Our algorithm can also be used to substantially improve existing algorithms for the Steiner minimal tree problem. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0196-6774(92)90050-M | J. Algorithms |
Keywords | DocType | Volume |
shortest network | Journal | 13 |
Issue | ISSN | Citations |
3 | 0196-6774 | 17 |
PageRank | References | Authors |
2.76 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. K. Hwang | 1 | 332 | 100.54 |
| J. F. Weng | 2 | 31 | 5.20 |