On paths with the shortest average arc length in weighted graphs

Abstract

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 considered in this paper. This problem arises in VLSI block placement procedures when spreading the building blocks uniformly over the chip area is attempted. A well-known approximation algorithm to find the path with the minimum weight-ratio in a doubly-weighted graph can solve this problem. It combines a combinatorial algorithm with numerical iterations and its time complexity is O({glottal stop}U{glottal stop}3 log 1/ε), where {glottal stop}U{glottal stop} is the number of vertices and ε is the desired accuracy. This paper presents two new algorithms. The first, called the path length minimization algorithm, is based on the same principles as the algorithm presented by Karp, and can also be applied to undirected graphs. It is purely combinatorial and has O({glottal stop}U{glottal stop}3) time complexity. We show how this algorithm for finding the path with the minimum average arc length can be extended to solve the more general problem of finding the path with the minimum weight-ratio in a doubly-weighted graph for which the secondary arc weights are positive integral or rational numbers. The second algorithm, called the vertex balancing algorithm, approximates the minimum average arc length path in any desired accuracy. It also combines a combinatorial algorithm with numerical iterations. Though having an exponential time complexity, it has been used successfully, achieving rapid convergence in all the practical cases which have been encountered. © 1993.