Directed shortest paths via approximate cost balancing
type: Item
instance of: scholarly article
title: Directed shortest paths via approximate cost balancing
DOI: 10.1145/3565019
author: James B. Orlin
author: László A. Végh
published in: Journal of the ACM
publication date: 2024-07-04T00:00:00Z
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7876156
zbMATH Keywords: shortest paths
zbMATH Keywords: cost balancing
zbMATH Keywords: component hierarchy
MaRDI profile type: MaRDI publication profile
cites work: Q3056948
cites work: Deterministic APSP, Orthogonal Vectors, and More
cites work: Q3651735
cites work: A note on two problems in connexion with graphs
cites work: Trans-dichotomous algorithms for minimum spanning trees and shortest paths
cites work: New Bounds on the Complexity of the Shortest Path Problem
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Scaling Algorithms for the Shortest Paths Problem
cites work: Q2754134
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Approximate binary search algorithms for mean cuts and cycles
cites work: New scaling algorithms for the assignment and minimum mean cycle problems
cites work: An O(nm) time algorithm for finding the min length directed cycle in a graph
cites work: On Pre-Conditioning of Matrices
cites work: Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration
cites work: Balancing a matrix for calculation of eigenvalues and eigenvectors
cites work: Q4425938
cites work: A new approach to all-pairs shortest paths on real-weighted graphs
cites work: Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
cites work: A Shortest Path Algorithm for Real-Weighted Undirected Graphs
cites work: Max-Balancing Weighted Directed Graphs and Matrix Scaling
cites work: Analysis of a Classical Matrix Preconditioning Algorithm
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Q3707420
cites work: Undirected single-source shortest paths with positive integer weights in linear time
cites work: Q4471360
cites work: Integer priority queues with decrease key in constant time and the single source shortest paths problem
cites work: A Theorem on Boolean Matrices
cites work: Faster all-pairs shortest paths via circuit complexity
cites work: Faster parametric shortest path and minimum‐balance algorithms
description: scientific article; zbMATH DE number 7876156