View in EDS PDF Full Text

An Improved Augmented Line Segment based Algorithm for the Generation of Rectilinear Steiner Minimum Tree.

Saved in:
Bibliographic Details
Title: An Improved Augmented Line Segment based Algorithm for the Generation of Rectilinear Steiner Minimum Tree.
Authors: V., Vani1 vanisrin@gmail.com, Prasad, G. R.2
Source: International Journal of Electrical & Computer Engineering (2088-8708). Jun2017, Vol. 7 Issue 3, p1262-1267. 6p.
Subjects: Line geometry, Very large scale circuit integration, Algorithms, Spanning trees, Cost control
Abstract: An improved Augmented Line Segment Based (ALSB) algorithm for the construction of Rectilinear Steiner Minimum Tree using augmented line segments is proposed. The proposed algorithm works by incrementally increasing the length of line segments drawn from all the points in four directions. The edges are incrementally added to the tree when two line segments intersect. The reduction in cost is obtained by postponing the addition of the edge into the tree when both the edges (upper and lower Lshaped layouts) are of same length or there is no overlap. The improvement is focused on reduction of the cost of the tree and the number of times the line segments are augmented. Instead of increasing the length of line segments by 1, the line segments length are doubled each time until they cross the intersection point between them. The proposed algorithm reduces the wire length and produces good reduction in the number of times the line segments are incremented. Rectilinear Steiner Minimum Tree has the main application in the global routing phase of VLSI design. The proposed improved ALSB algorithm efficiently constructs RSMT for the set of circuits in IBM benchmark. [ABSTRACT FROM AUTHOR]
Copyright of International Journal of Electrical & Computer Engineering (2088-8708) is the property of Institute of Advanced Engineering & Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 129326395
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: An Improved Augmented Line Segment based Algorithm for the Generation of Rectilinear Steiner Minimum Tree.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22V%2E%2C+Vani%22">V., Vani</searchLink><relatesTo>1</relatesTo><i> vanisrin@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Prasad%2C+G%2E+R%2E%22">Prasad, G. R.</searchLink><relatesTo>2</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Electrical+%26+Computer+Engineering+%282088-8708%29%22">International Journal of Electrical & Computer Engineering (2088-8708)</searchLink>. Jun2017, Vol. 7 Issue 3, p1262-1267. 6p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Line+geometry%22">Line geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Very+large+scale+circuit+integration%22">Very large scale circuit integration</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Spanning+trees%22">Spanning trees</searchLink><br /><searchLink fieldCode="DE" term="%22Cost+control%22">Cost control</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: An improved Augmented Line Segment Based (ALSB) algorithm for the construction of Rectilinear Steiner Minimum Tree using augmented line segments is proposed. The proposed algorithm works by incrementally increasing the length of line segments drawn from all the points in four directions. The edges are incrementally added to the tree when two line segments intersect. The reduction in cost is obtained by postponing the addition of the edge into the tree when both the edges (upper and lower Lshaped layouts) are of same length or there is no overlap. The improvement is focused on reduction of the cost of the tree and the number of times the line segments are augmented. Instead of increasing the length of line segments by 1, the line segments length are doubled each time until they cross the intersection point between them. The proposed algorithm reduces the wire length and produces good reduction in the number of times the line segments are incremented. Rectilinear Steiner Minimum Tree has the main application in the global routing phase of VLSI design. The proposed improved ALSB algorithm efficiently constructs RSMT for the set of circuits in IBM benchmark. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of International Journal of Electrical & Computer Engineering (2088-8708) is the property of Institute of Advanced Engineering & Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=129326395
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.11591/ijece.v7i3.pp1262-1267
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 6
        StartPage: 1262
    Subjects:
      – SubjectFull: Line geometry
        Type: general
      – SubjectFull: Very large scale circuit integration
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Spanning trees
        Type: general
      – SubjectFull: Cost control
        Type: general
    Titles:
      – TitleFull: An Improved Augmented Line Segment based Algorithm for the Generation of Rectilinear Steiner Minimum Tree.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: V., Vani
      – PersonEntity:
          Name:
            NameFull: Prasad, G. R.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 20888708
          Numbering:
            – Type: volume
              Value: 7
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: International Journal of Electrical & Computer Engineering (2088-8708)
              Type: main
ResultId 1