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 language | English (US) |
|---|---|
| Pages | 687-690 |
| Number of pages | 4 |
| State | Published - 2004 |
| Event | Proceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004 - Yokohama, Japan Duration: Jan 27 2004 → Jan 30 2004 |
Other
| Other | Proceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004 |
|---|---|
| Country/Territory | Japan |
| City | Yokohama |
| Period | 1/27/04 → 1/30/04 |
ASJC Scopus subject areas
- Computer Science Applications
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering