Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs

DOI10.1016/J.JDA.2013.03.005zbMATH Open1334.05162OpenAlexW2005720192MaRDI QIDQ396709FDOQ396709

Authors: Domenico Cantone, Simone Faro 

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

Recommendations

• Speeding up shortest path algorithms
• Shortest paths in almost acyclic graphs
• scientific article; zbMATH DE number 2086613
• Optimally fast shortest path algorithms for some classes of graphs
• Hybrid Bellman-Ford-Dijkstra algorithm

zbMATH Keywords

computational complexityshortest pathnegative edges

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Cites Work

• A note on two problems in connexion with graphs
• Introduction to algorithms
• Generalized Nested Dissection
• On a routing problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Efficient Algorithms for Shortest Paths in Sparse Networks
• A new approach to all-pairs shortest paths on real-weighted graphs
• More algorithms for all-pairs shortest paths in weighted graphs
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• The shortest-path problem for graphs with random arc-lengths
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• A new upper bound on the complexity of the all pairs shortest path problem
• Improved algorithm for all pairs shortest paths
• An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
• Undirected single-source shortest paths with positive integer weights in linear time
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• Algorithms and Data Structures
• Algorithms and Computation
• Two-Levels-Greedy: a generalization of Dijkstra's shortest path algorithm
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• 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
• All-pairs shortest paths and the essential subgraph
• A heuristic improvement of the Bellman-Ford algorithm
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Shortest paths in directed planar graphs with negative lengths
• On Shortest Paths in Graphs with Random Weights
• Shortest‐path methods: Complexity, interrelations and new propositions
• Computing and Combinatorics
• Implementation and efficiency of Moore-algorithms for the shortest route problem
• An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
• A Note on Dijkstra's Shortest Path Algorithm
• Faster shortest-path algorithms for planar graphs

Cited In (4)

• Title not available (Why is that?)
• Shortest paths in almost acyclic graphs
• An integrated approach for earthwork allocation, sequencing and routing
• Shortest paths in directed planar graphs with negative lengths

Uses Software

• Algorithm 97

This page was built for publication: Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396709)