Constructing minimal spanning trees with lower and upper bounded path delays

This paper presents an algorithm for solving the Lower and Upper Bounded delay Minimal Spanning Tree (LUBMST) problem. The proposed heuristic method is based on the classical Kruskal MST construction. For any given value of parameters ε₁ and ε₂, the algorithm constructs a routing tree with the shortest interconnection path length at least ε₁·R and the longest interconnection path length at most (1+ε₂)·R, where R is the length of the direct path from the source to the farthest sink. Extension of these techniques to the Elmore delay model is presented as well. Empirical results demonstrate the effectiveness of these algorithms on a large benchmark set