Faster Parametric Shortest Path and Minimum Balance Algorithms

Abstract

The parametric shortest path problem is to find the shortest paths in graph where the edge costs are of the form w_ij+lambda where each w_ij is constant and lambda is a parameter that varies. The problem is to find shortest path trees for every possible value of lambda. The minimum-balance problem is to find a ``weighting'' of the vertices so that adjusting the edge costs by the vertex weights yields a graph in which, for every cut, the minimum weight of any edge crossing the cut in one direction equals the minimum weight of any edge crossing the cut in the other direction. The paper presents fast algorithms for both problems. The algorithms run in O(nm+n^2 log n) time. The paper also describes empirical studies of the algorithms on random graphs, suggesting that the expected time for finding a minimum-mean cycle (an important special case of both problems) is O(n log(n) + m).

Cited by in corpus (19)

• On visualisation scaling, subeigenvectors and Kleene stars in max algebra
• Setting Parameters by Example
• A Survey of Shortest-Path Algorithms
• A General Approximation Method for Bicriteria Minimization Problems
• Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
• Discovering Interesting Cycles in Directed Graphs
• Multiple-Source Shortest Paths in Embedded Graphs
• Analysis of a Classical Matrix Preconditioning Algorithm
• The min mean-weight cycle in a random network
• Periodic trajectories in P-time event graphs and the non-positive circuit weight problem
• The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory
• Supercritical minimum mean-weight cycles
• Approximating the minimum cycle mean
• An Algorithmic Perspective on Some Network Design, Construction and Analysis Problems
• An FPTAS for the parametric knapsack problem
• Two-phase algorithms for the parametric shortest path problem
• New Algorithmic Approaches for Computing Optimal Network Paths with Several Types of QoS Constraints
• Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration
• An FPTAS for the Knapsack Problem with Parametric Weights