Article Sidebar
Published:
Jun 17, 2005Keywords:
Steiner ratio Steiner tree spanning tree rectilinear tree L<sub>1</sub> norm NP-complete
Article Details
Issue
Section
Articles
The following license applies:
Attribution CC BY
This license lets others distribute, remix, tweak, and build upon your work, even commercially, as long as they credit you for the original creation.
Main Article Content
The rectilinear Steiner ratio
Abstract
The rectilinear Steiner ratio was shown to be 3/2 by Hwang [Hwang FK, 1976, On Steiner minimal trees with rectilinear distance, SIAM Journal on Applied Mathematics, 30, pp. 104–114.]. We use continuity and introduce restricted point sets to obtain an alternative, short and self-contained proof of this result.
Key words: Steiner ratio, Steiner tree, spanning tree, rectilinear tree, L1 norm, NP-complete.
ORiON Vol.21(1) 2005: 53-61
Key words: Steiner ratio, Steiner tree, spanning tree, rectilinear tree, L1 norm, NP-complete.
ORiON Vol.21(1) 2005: 53-61
