A New Polynomially Bounded Shortest Path Algorithm

DOI10.1287/OPRE.33.1.65MaRDI QIDQ3701214zbMATH OpenOpenAlexFDO

Authors Fred Glover, Darwin D. Klingman, Nancy V. Phillips

Publication date 1985

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.33.1.65

zbMATH Keywords

label correcting algorithmslabel setting algorithmpartitioning shortest pathpolynomially bounded shortest path algorithmthreshold algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• New Polynomial Shortest Path Algorithms and Their Computational Attributes
• A note on the partitioning shortest path algorithm
• A new variant of the partitioning shortest path algorithm
• scientific article; zbMATH DE number 1093953
• Shortest path algorithms using dynamic breadth‐first search

Cited in

(30)

• An extension of labeling techniques for finding shortest path trees
• Microcomputer-based algorithms for large scale shortest path problems
• A new variant of the partitioning shortest path algorithm
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Improvements for the thresh X2 shortest path algorithm
• A note on the partitioning shortest path algorithm
• A computational study of efficient shortest path algorithms
• Shortest path algorithms: A computational study with the C programming language
• Minisum amd minimax paths of a moving facility on a network
• Some personal views on the current state and the future of locational analysis
• Time depending shortest-path problems with applications to railway networks
• Efficient algorithms for some path partitioning problems
• Intelligent transportation systems -- Enabling technologies
• Shortest paths algorithms: Theory and experimental evaluation
• A new approximation algorithm for obtaining the probability distribution function for project completion time
• Heuristic shortest path algorithms for transportation applications: state of the art
• On the equivalence between some shortest path algorithms
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Solving the nearly symmetric all-pairs shortest-path problem
• New Polynomial Shortest Path Algorithms and Their Computational Attributes
• New Sharpness Properties, Algorithms and Complexity Bounds for Partitioning Shortest Path Procedures
• An efficient label setting/correcting shortest path algorithm
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Scheduling and routing algorithms for AGVs: A survey
• Parallel solutions of static Hamilton-Jacobi equations for simulations of geological folds
• Route planning for automated guided vehicles in a manufacturing facility
• Maximum outflow in generalized flow networks
• A simplification of the double-sweep algorithm to solve the \(k\)-shortest path problem
• A novel pseudo‐polynomial approach for shortest path problems
• A new \(O(n^ 2)\) shortest chain algorithm

This page was built for publication: A New Polynomially Bounded Shortest Path Algorithm

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