Abstract.
In 1992 F. K. Hwang and J. F. Weng published an O(n 2 ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n 2 ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received August 24, 1996; revised February 10, 1997.
Rights and permissions
About this article
Cite this article
Xue, G., Du, DZ. An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology . Algorithmica 23, 354–362 (1999). https://doi.org/10.1007/PL00009266
Issue Date:
DOI: https://doi.org/10.1007/PL00009266