Title :
On better heuristic for Euclidean Steiner minimum trees
Author :
Du, Ding-Zhu ; Zhang, Yanjun ; Feng, Qing
Abstract :
Finding a shortest network interconnecting a given set of points in the Euclidean plane (a Steiner minimum tree) is known to be NP-hard. It is shown that there exists a polynomial-time heuristic with a performance ratio bigger than √3/2
Keywords :
computational complexity; computational geometry; trees (mathematics); Euclidean Steiner minimum trees; NP-hard; polynomial-time heuristic; shortest network; Approximation algorithms; Civil engineering; Computer science; Extraterrestrial measurements; Mathematics; NP-hard problem; Operations research; Polynomials; Steiner trees; Surface-mount technology;
Conference_Titel :
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location :
San Juan
Print_ISBN :
0-8186-2445-0
DOI :
10.1109/SFCS.1991.185402
