Efficient octilinear steiner tree construction based on spanning graphs

Qi Zhu*, Hai Zhou, Tong Jing, Xianlong Hong, Yang Yang

*Corresponding author for this work

Research output: Contribution to conferencePaper

12 Scopus citations

Abstract

Octilinear interconnect is a promising technique to shorten wire lengths. We present two practical heuristic octilinear Steiner tree (OSMT) algorithms in the paper. They are both based on octilinear spanning graphs. The one by edge substitution (OST-E) has a worst case running time of O(nlogn) and similar performance as the batched greedy algorithm. The other one by triangle contraction (OST-T) has a small increase in running time and better performance. Experiments on both industry and random test cases are conducted.

Original languageEnglish (US)
Pages687-690
Number of pages4
StatePublished - Jun 1 2004
EventProceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004 - Yokohama, Japan
Duration: Jan 27 2004Jan 30 2004

Other

OtherProceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004
CountryJapan
CityYokohama
Period1/27/041/30/04

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Efficient octilinear steiner tree construction based on spanning graphs'. Together they form a unique fingerprint.

  • Cite this

    Zhu, Q., Zhou, H., Jing, T., Hong, X., & Yang, Y. (2004). Efficient octilinear steiner tree construction based on spanning graphs. 687-690. Paper presented at Proceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004, Yokohama, Japan.