Please use this identifier to cite or link to this item: http://hdl.handle.net/20.500.11861/7664
Title: Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems
Authors: Li Y.Y. 
Prof. LEUNG Kwong Sak 
Wong C.K. 
Issue Date: 2000
Publisher: Springer Netherlands
Source: Journal of Combinatorial Optimization, 2000, vol. 4 (1), pp. 79 - 98
Journal: Journal of Combinatorial Optimization 
Abstract: We consider Steiner minimum trees (SMT) in the plane, where only orientations with angle iπ/σ, 0 ≤ i ≤; σ - 1 and σ an integer, are allowed. The orientations define a metric, called the orientation metric, λσ, in a natural way. In particular, λ2 metric is the rectilinear metric and the Euclidean metric can be regarded as λ∞ metric. In this paper, we provide a method to find an optimal λσ SMT for 3 or 4 points by analyzing the topology of λσ SMT's in great details. Utilizing these results and based on the idea of loop detection first proposed in Chao and Hsu, IEEE Trans. CAD, vol. 13, no. 3, pp. 303-309, 1994, we further develop an O(n2) time heuristic for the general λσ SMT problem, including the Euclidean metric. Experiments performed on publicly available benchmark data for 12 different metrics, plus the Euclidean metric, demonstrate the efficiency of our algorithms and the quality of our results.
Type: Peer Reviewed Journal Article
URI: http://hdl.handle.net/20.500.11861/7664
ISSN: 13826905
DOI: 10.1023/A:1009837006569
Appears in Collections:Applied Data Science - Publication

Show full item record

SCOPUSTM   
Citations

5
checked on Nov 17, 2024

Page view(s)

30
Last Week
0
Last month
checked on Nov 21, 2024

Google ScholarTM

Impact Indices

Altmetric

PlumX

Metrics


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.