Share Email Print
cover

Proceedings Paper

A restricted Steiner tree problem is solved by Geometric Method II
Author(s): Dazhi Lin; Youlin Zhang; Xiaoxu Lu
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

The minimum Steiner tree problem has wide application background, such as transportation system, communication network, pipeline design and VISL, etc. It is unfortunately that the computational complexity of the problem is NP-hard. People are common to find some special problems to consider. In this paper, we first put forward a restricted Steiner tree problem, which the fixed vertices are in the same side of one line L and we find a vertex on L such the length of the tree is minimal. By the definition and the complexity of the Steiner tree problem, we know that the complexity of this problem is also Np-complete. In the part one, we have considered there are two fixed vertices to find the restricted Steiner tree problem. Naturally, we consider there are three fixed vertices to find the restricted Steiner tree problem. And we also use the geometric method to solve such the problem.

Paper Details

Date Published: 20 March 2013
PDF: 5 pages
Proc. SPIE 8768, International Conference on Graphic and Image Processing (ICGIP 2012), 87680H (20 March 2013); doi: 10.1117/12.2010624
Show Author Affiliations
Dazhi Lin, Zhengzhou College of Animal Husbandry Engineering (China)
Youlin Zhang, Zhengzhou Institute of Aeronautical Industry Management (China)
Xiaoxu Lu, Zhengzhou Institute of Aeronautical Industry Management (China)


Published in SPIE Proceedings Vol. 8768:
International Conference on Graphic and Image Processing (ICGIP 2012)
Zeng Zhu, Editor(s)

© SPIE. Terms of Use
Back to Top