A restricted Steiner tree problem is solved by Geometric Method II

Dazhi Lin; Youlin Zhang; Xiaoxu Lu

doi:10.1117/12.2010624

20 March 2013 A restricted Steiner tree problem is solved by Geometric Method II

Dazhi Lin, Youlin Zhang, Xiaoxu Lu

Proceedings Volume 8768, International Conference on Graphic and Image Processing (ICGIP 2012); 87680H (2013) https://doi.org/10.1117/12.2010624
Event: 2012 International Conference on Graphic and Image Processing, 2012, Singapore, Singapore

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.

Citation Download Citation

Dazhi Lin, Youlin Zhang, and Xiaoxu Lu "A restricted Steiner tree problem is solved by Geometric Method II", Proc. SPIE 8768, International Conference on Graphic and Image Processing (ICGIP 2012), 87680H (20 March 2013); https://doi.org/10.1117/12.2010624

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available