Algorithmic Approach for Creating and Exploiting Flexibility in Steiner Trees
Piyush Singh, Animesh Pant
Abstract
Routing is an important task in VLSI design and the rectilinear Steiner minimal tree (RSMT) construction is a fundamental research issue in the context of routing. Given a set of terminals, the RSMT problem is to find a rectilinear minimum spanning tree (RMST) that connects all the terminals, possibly through some additional points (called Steiner points) with minimal length. In practice, rectilinear Steiner trees are used to route signal nets by global and detail routers. Steiner tree problem is not just only routing problems in Computer networks it can also be used in designing proper road, airway routes. The concept of minimization of Steiner trees have practical applications in field of VLSI Routing, Wire length estimation, as all required minimization of intersections. Minimization of intersection can be achieved by creating and Exploiting flexibility in Steiner trees. But producing Flexibility in RST can produce such set with minimum number of intersections. The new, flexible tree is guaranteed to have the same total length. Any existing Steiner tree algorithm can be used for the initial construction of the Steiner tree. While solving for the flexibility in Steiner tree, problems like dealing with the overlaps have to be tackled and maximizing the flexibility has to done.
Full Text:
PDF
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