A lower bound for the shortest path problem

DOI10.1006/JCSS.2001.1766MaRDI QIDQ5956014zbMATH OpenOpenAlexFDO

Authors Ketan D. Mulmuley, Pradyut Shah

Publication date 22 July 2002

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2001.1766

zbMATH Keywords

repeated squaring algorithmshortest path problem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Recommendations

• New Bounds on the Complexity of the Shortest Path Problem
• scientific article; zbMATH DE number 1962826
• On the difficulty of some shortest path problems
• A new upper bound on the complexity of the all pairs shortest path problem
• scientific article; zbMATH DE number 219247

Cites work

• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• An \NC Algorithm for Minimum Cuts
• An application of simultaneous diophantine approximation in combinatorial optimization
• An O(n2log n) parallel max-flow algorithm
• Complexity of some parametric integer and network programming problems
• Fast Parallel Matrix Inversion Algorithms
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Matching is as easy as matrix inversion
• Matching theory
• Probabilistic parallel prefix computation
• Specified precision polynomial root isolation is in NC

Cited in

(12)

• An explicit lower bound for TSP with distances one and two
• Analysis of FPTASes for the multi-objective shortest path problem
• Bounds and heuristics for the shortest capacitated paths problem
• An approximation algorithm for a general class of multi-parametric optimization problems
• An approximation algorithm for a general class of parametric optimization problems
• Theoretical lower bound for border length minimization problem
• On the optimality of Bellman-Ford-Moore shortest path algorithm
• A lower bound for the quickest path problem
• Approximation schemes for the parametric knapsack problem
• Shadows of Newton polytopes
• Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
• A survey of exact and approximation algorithms for linear-parametric optimization problems

This page was built for publication: A lower bound for the shortest path problem

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