Scaling Algorithms for the Shortest Paths Problem
From MaRDI portal
Publication:4842117
DOI10.1137/S0097539792231179zbMath0831.68046OpenAlexW2164141517MaRDI QIDQ4842117
Publication date: 26 July 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792231179
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)
Related Items
Fair matchings and related problems ⋮ A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Event counting of partially-observed discrete-event systems with uniformly and nonuniformly bounded diagnosis delays ⋮ Unnamed Item ⋮ Separation, dimension, and facet algorithms for node flow polyhedra ⋮ Variants of Multi-resource Scheduling Problems with Equal Processing Times ⋮ Multi-agent differential graphical games: online adaptive learning solution for synchronization with optimality ⋮ Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs ⋮ A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs ⋮ On the analysis of optimization problems in arc-dependent networks ⋮ Randomized algorithms for finding the shortest negative cost cycle in networks ⋮ Approximate shortest paths in weighted graphs ⋮ Minimum-cost flows in unit-capacity networks ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ Improved algorithms for optimal length resolution refutation in difference constraint systems ⋮ Solving mean-payoff games via quasi dominions ⋮ Trichotomy for integer linear systems based on their sign patterns ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ An efficient label setting/correcting shortest path algorithm ⋮ A zero-space algorithm for negative cost cycle detection in networks ⋮ Finding real-valued single-source shortest paths in o(n 3) expected time ⋮ Hybrid Bellman-Ford-Dijkstra algorithm ⋮ Approximating the minimum cycle mean ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Faster shortest-path algorithms for planar graphs ⋮ Unnamed Item ⋮ Unpopularity factor in the marriage and roommates problems ⋮ A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints ⋮ Intermittent fault diagnosability of discrete event systems: an overview of automaton-based approaches ⋮ Maximum weight bipartite matching in matrix multiplication time ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls ⋮ On the \(K\) shortest path trees problem ⋮ Finding the k Shortest Paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Feasibility checking in Horn constraint systems through a reduction based approach
