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 considered. 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(| U|^ 3\log 1/\varepsilon)\), where \(| U|\) is the number of vertices and \(\varepsilon\) is the desired accuracy. The paper presents two new algorithms. The first, called the path length minimization algorithm, is based on the same principles as the algorithm presented by \textit{R. M. Karp} [Discrete Math. 23, 309-311 (1978; Zbl 0386.05032)] and can also be applied to undirected graphs. It is purely combinatorial and has \(O(| U|^ 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.
- Shortest paths in a diagraph with an underestimated arc weight
- Approximate shortest paths in weighted graphs
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- The shortest-path problem for graphs with random arc-lengths
- scientific article; zbMATH DE number 936862
- On Shortest Paths in Graphs with Random Weights
- On finding shortest paths in arc-dependent networks
- scientific article; zbMATH DE number 56364
- Shortest path network problems with stochastic arc weights
- Shortest paths in random weighted graphs
- A pseudo-polynomial algorithm for detecting minimum weighted length paths in a network
- Paths with minimum range and ratio of arc lengths
- Finding a contour with the smallest mean expenses in a graph with variable arc lengths. The simplest case
- Algorithms for finding paths with multiple constraints
- On the average length of lexicographic paths
- A primal-dual algorithm for the minimum average weighted length circuit problem
- scientific article; zbMATH DE number 1052832 (Why is no real title available?)
This page was built for publication: On paths with the shortest average arc length in weighted graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686427)
