Title: Steiner Trees, Coordinate Systems and NP-Hardness
Abstract: Given a set A of points a 1, a 2,..., in the Euclidean plane, the Steiner tree problem asks for a minimum network T(A) (or T if A is not necessarily mentioned) interconnecting A with some additional points to shorten the network [6]. The given points are referred to as terminals and the additional points are referred to as Steiner points. Trivially, T is a tree, called the Euclidean Steiner minimal tree (ESMT) for A. It is well known that Steiner minimal trees satisfy an angle condition: all angles at the vertices of Steiner minimal trees are not less than 120° [6]. A tree satisfying this angle condition is called a Steiner tree. Therefore, a Steiner minimal tree must be a Steiner tree.
Publication Year: 2000
Publication Date: 2000-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot