International Journal of Emerging Trends & Technology in Computer Science
A Motivation for Recent Innovation & Research
ISSN 2278-6856
www.ijettcs.org

Call for Paper, Published Articles, Indexing Infromation Rectilinear Steiner Minimum Tree Formation using an Improved Augmented Line Segment Based Algorithm with Edge Reversal, Authors : Vani V and G R Prasad, International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), www.ijettcs.org
Volume & Issue no: Volume 7, Issue 1, January - February 2018

Title:
Rectilinear Steiner Minimum Tree Formation using an Improved Augmented Line Segment Based Algorithm with Edge Reversal
Author Name:
Vani V and G R Prasad
Abstract:
Abstract An improvement to Augmented Line Segment Based Algorithm is proposed incorporating Edge reversal to generate a Rectilinear Steiner Minimum Tree with an objective of tree length reduction. Rectilinear Steiner Minimum Tree connects the given collection of points by means of horizontal and vertical line segments, with the aid of additional points called Steiner Points. Steiner points are introduced to reduce the total length of the tree and to connect in rectilinear manner since the distance between two points is measured in rectilinear metric. The algorithm constructs a Rectilinear Steiner Minimum Tree by augmenting the line segments drawn in four directions from all the points and adding an edge to the tree when two line segments overlap. The reversal of the two L-shaped layouts or edges is done when an overlap count of either of one increases thereby reducing the cost or length of the final tree formed. Rectilinear Steiner Minimum Tree is widely used in global routing phase of VLSI design and wire length estimation. Keywords: Rectilinear Steiner Minimum Tree, Global Routing, Rectilinear Minimum Spanning Tree, VLSI Design
Cite this article:
Vani V and G R Prasad , " Rectilinear Steiner Minimum Tree Formation using an Improved Augmented Line Segment Based Algorithm with Edge Reversal " , International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), Volume 7, Issue 1, January - February 2018 , pp. 001-004 , ISSN 2278-6856.
Full Text [PDF]                          Home