DocumentCode :
554978
Title :
The longest side elimination solution for solving Steiner minimum tree problems
Author :
Li-Li Xu ; Zong-Xiao Yang ; You-Lin Shang ; Ting-Ting Wang
Author_Institution :
Henan Univ. of Sci. & Technol., Luoyang, China
fYear :
2011
fDate :
11-13 Aug. 2011
Firstpage :
245
Lastpage :
249
Abstract :
The Steiner minimum tree (SMT) problem is one of the classic nonlinear combinatorial optimization problems for centuries. A novel solution, longest side elimination solution method (LSEM), is proposed in this paper. Firstly, the minimum spanning trees is defined as convex road and external side. Secondly, LSESM is constructed for solving the full SMT by using Melzak geometric composition principle to choose several points convex road which can satisfied certain conditions in the minimum spanning tree. And lastly, we can construct point set´s full SMT according to visualization experiment results and Melzak geometric composition principle, combining with LSEM. A subsection-inserting points algorithm (SIPA) is described for eliminating the longest side in the convex road and solving the system shortest path sequentially. The global shortest path can be obtained by SIPA successfully compared with experimental results of visualization instrument.
Keywords :
computational complexity; optimisation; trees (mathematics); Melzak geometric composition principle; Steiner minimum tree problem; convex road; external side; global shortest path; longest side elimination solution method; minimum spanning tree; nonlinear combinatorial optimization problem; subsection-inserting points algorithm; visualization instrument; Mechatronics; Roads; Visualization; Convex road; External side; Longest side elimination method(LSEM); Minimum spanning tree (MST); Steiner minimum tree(SMT); Subsection-inserting points algorithm (SIPA);
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Advanced Mechatronic Systems (ICAMechS), 2011 International Conference on
Conference_Location :
Zhengzhou
Print_ISBN :
978-1-4577-1698-0
Type :
conf
Filename :
6025022
Link To Document :
بازگشت