Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
From MaRDI portal
Publication:396709
DOI10.1016/j.jda.2013.03.005zbMath1334.05162OpenAlexW2005720192MaRDI QIDQ396709
Publication date: 13 August 2014
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2013.03.005
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- The shortest-path problem for graphs with random arc-lengths
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A new upper bound on the complexity of the all pairs shortest path problem
- A bidirectional shortest-path algorithm with good average-case behavior
- A hybrid algorithm for the shortest path between two nodes in the presence of few negative arcs
- A new approach to all-pairs shortest paths on real-weighted graphs
- All-pairs shortest paths and the essential subgraph
- A heuristic improvement of the Bellman-Ford algorithm
- Improved algorithm for all pairs shortest paths
- Planar graphs, negative weight edges, shortest paths, and near linear time
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- Undirected single-source shortest paths with positive integer weights in linear time
- On a routing problem
- Two-Levels-Greedy: a generalization of Dijkstra's shortest path algorithm
- More algorithms for all-pairs shortest paths in weighted graphs
- On Shortest Paths in Graphs with Random Weights
- Shortest‐path methods: Complexity, interrelations and new propositions
- Generalized Nested Dissection
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Computing and Combinatorics
- Implementation and efficiency of Moore-algorithms for the shortest route problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Algorithms and Data Structures
- An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
- A Note on Dijkstra's Shortest Path Algorithm
- Algorithms and Computation
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
