Efficient Shortest Path Simplex Algorithms

DOI10.1287/OPRE.38.4.624MaRDI QIDQ5202040zbMATH OpenOpenAlexFDO

Authors Donald Goldfarb, Jianxiu Hao, Sheng-Roan Kai

Publication date 1990

Published in Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

labelingworst-case boundshortest path simplex algorithmlabel- correcting algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• New efficient shortest path simplex algorithm: Pseudo permanent labels instead of permanent labels
• An \(O(nm)\)-time network simplex algorithm for the shortest path problem
• Shortest path methods: A unifying approach
• Shortest path algorithms using dynamic breadth‐first search
• A note on the partitioning shortest path algorithm

Cited in

(18)

• ON SOLVING SHORTEST PATHS WITH A LEAST-SQUARES PRIMAL-DUAL ALGORITHM
• SHORTEST PATH SIMPLEX ALGORITHM WITH A MULTIPLE PIVOT RULE: A COMPARATIVE STUDY
• A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
• A friendly smoothed analysis of the simplex method
• scientific article; zbMATH DE number 1472107 (Why is no real title available?)
• Efficient Algorithms for Solving the Shortest Covering Path Problem
• A polynomial time primal network simplex algorithm for minimum cost flows
• New efficient shortest path simplex algorithm: Pseudo permanent labels instead of permanent labels
• A new pivot selection rule for the network simplex algorithm
• Exterior point simplex-type algorithms for linear and network optimization problems
• On the \(K\) shortest path trees problem
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• The single most vital arc in the most economical path problem -- a parametric analysis
• An \(O(nm)\)-time network simplex algorithm for the shortest path problem
• scientific article; zbMATH DE number 4158666 (Why is no real title available?)
• Algorithms and Computation
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• The fuzzy shortest path problem and its most vital arcs

This page was built for publication: Efficient Shortest Path Simplex Algorithms

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