IEICE TRANSACTIONS on Fundamentals
Cost-Radius Balanced Spanning/Steiner Trees
Summary :
The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.4 pp.689-694
- Publication Date
- 1997/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hideki MITSUBAYASHI, Atsushi TAKAHASHI, Yoji KAJITANI, "Cost-Radius Balanced Spanning/Steiner Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 4, pp. 689-694, April 1997, doi: .
Abstract: The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_4_689/_p
Copy
@ARTICLE{e80-a_4_689,
author={Hideki MITSUBAYASHI, Atsushi TAKAHASHI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Cost-Radius Balanced Spanning/Steiner Trees},
year={1997},
volume={E80-A},
number={4},
pages={689-694},
abstract={The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Cost-Radius Balanced Spanning/Steiner Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 689
EP - 694
AU - Hideki MITSUBAYASHI
AU - Atsushi TAKAHASHI
AU - Yoji KAJITANI
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1997
AB - The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.
ER -
English
