ON PATHS WITH THE SHORTEST AVERAGE ARC LENGTH IN WEIGHTED GRAPHS

The problem of finding the path having the smallest average arc length in an acyclic digraph with a single source and a single sink is consi dered in this paper. This problem arises in VLSI block placement proce dures when spreading the building blocks uniformly over the chip area is attempted. A well-known approximation algorithm to find the path wi th the minimum weight-ratio in a doubly-weighted graph can solve this problem. It combines a combinatorial algorithm with numerical iteratio ns and its time complexity is O(Absolute value of U3 log 1/epsilon), w here Absolute value of U is the number of vertices and epsilon is the desired accuracy. This paper presents two new algorithms. The first, c alled the path length minimization algorithm, is based on the same pri nciples as the algorithm presented by Karp, and can also be applied to undirected graphs. It is purely combinatorial and has O(Absolute valu e of U3) time complexity. We show how this algorithm for finding the p ath with the minimum average arc length can be extended to solve the m ore general problem of finding the path with the minimum weight-ratio in a doubly-weighted graph for which the secondary arc weights are pos itive integral or rational numbers. The second algorithm, called the v ertex balancing algorithm, approximates the minimum average arc length path in any desired accuracy. It also combines a combinatorial algori thm with numerical iterations. Though having an exponential time compl exity, it has been used successfully, achieving rapid convergence in a ll the practical cases which have been encountered.