Global Journal of Computer Science and Technology, Vol 9, No 4 (2009)

Font Size:  Small  Medium  Large

A new approach to: Obstacle-Avoiding Rectilinear Steiner Tree Construction

Animesh Pant

Abstract


Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner tree(OARST) connects these points, possibly through some additional points(called Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wire length. The OARST problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity. Based on Obstacle-avoiding Spanning Graph (OASG), and edge based heuristic method has been applied to find the rectilinear Steiner tree with minimum wire length .



Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Copyright © 2001-2010 by Global Journals Inc. (US) – All Rights ReservedThe use of this site, and the terms and conditions for our providing information, is governed by our Disclaimer, Terms and Conditions and Privacy Policy.By using this site, this signifies and you acknowledge that you have read them and that you accept and will be bound by the terms thereof.All information, activities undertaken, materials, services and this website is subject to change anytime without any prior notice.


Best Viewed on FireFox Browsers with Flash Player and Resolution more than or equals 1024x768

USA Incorporation No.: 0423089  |  USA Tax ID (Employer ID No.): 098-0673227  |  License No.: 42125/022010/1186  |  Registration No.: 430374  |  Import-Export Code: 1109007027