Efficient Shortest Path Simplex Algorithms

DOI10.1287/OPRE.38.4.624zbMATH Open0723.90083OpenAlexW2013627567MaRDI QIDQ5202040FDOQ5202040

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

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

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)

Cited In (18)

• A friendly smoothed analysis of the simplex method
• A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
• Title not available (Why is that?)
• 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
• On the \(K\) shortest path trees problem
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• Exterior point simplex-type algorithms for linear and network optimization problems
• 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
• Title not available (Why is that?)
• 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
• ON SOLVING SHORTEST PATHS WITH A LEAST-SQUARES PRIMAL-DUAL ALGORITHM
• SHORTEST PATH SIMPLEX ALGORITHM WITH A MULTIPLE PIVOT RULE: A COMPARATIVE STUDY

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)