Country
USA
paper
SALT: Provably good routing topology by a novel steiner shallow-light tree algorithm
Publication Date:
Publication Date
16 November 2017
paper Menu
Abstract
In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates (i) shortest distances from a root to the other vertices, and (ii) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one [1], [2]. In this paper, we propose a novel Steiner SLT construction method called SALT (Steiner shAllow-Light Tree), which is efficient and has the tightest bound over all the state-of-the-art SLT algorithms. Applying SALT to Manhattan space offers a smooth trade-off between rectilinear Steiner minimum tree (RSMT) and rectilinear Steiner minimum arborescence (RSMA) for VLSI routing. In addition, the adaption further reduces the time complexity from O(n 2 ) to O(n log n). The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.
Country
HKG
Affiliation
Chinese University of Hong Kong
IEEE Region
Region 10 (Asia and Pacific)
Email
Affiliation
The Chinese University of Hong Kong
IEEE Region
Region 10 (Asia and Pacific)
Email