A faster algorithm for the single source shortest path problem with few distinct positive lengths

DOI10.1016/J.JDA.2009.03.001MaRDI QIDQ972360zbMATH OpenOpenAlexWikidataFDO

Authors James B. Orlin, Kamesh Madduri, K. Subramani, Matthew Williamson

Publication date 25 May 2010

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2009.03.001

zbMATH Keywords

Dijkstra's algorithmlinear timered-blue graphsshortest path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Undirected single-source shortest paths with positive integer weights in linear time
• A novel single source shortest path algorithm
• A new algorithm for the shortest-path problem
• scientific article; zbMATH DE number 1926665
• scientific article; zbMATH DE number 613343

Cites work

• A note on two problems in connexion with graphs
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 1875419 (Why is no real title available?)
• Introduction to algorithms
• Network flows. Theory, algorithms, and applications.
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

Cited in

(14)

• Locality-based relaxation: an efficient method for GPU-based computation of shortest paths
• A simple ant colony optimizer for stochastic shortest path problems
• A new algorithm for the minimum spanning tree verification problem
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Simpler computation of single-source shortest paths in linear average time
• Undirected single-source shortest paths with positive integer weights in linear time
• A novel single source shortest path algorithm
• Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment
• Running time analysis of ant colony optimization for shortest path problems
• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Using petal-decompositions to build a low stretch spanning tree
• scientific article; zbMATH DE number 7121921 (Why is no real title available?)
• Computing single source shortest paths using single-objective fitness
• An algorithmic framework for the single source shortest path problem with applications to disk graphs

Describes a project that uses

Uses Software

• Netsoft
• DIMACS

This page was built for publication: A faster algorithm for the single source shortest path problem with few distinct positive lengths

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