A lower bound for the shortest path problem
From MaRDI portal
Publication:5956014
DOI10.1006/jcss.2001.1766zbMath0988.68123OpenAlexW2146189710MaRDI QIDQ5956014
Pradyut Shah, Ketan D. Mulmuley
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
Related Items (7)
Distance oracles for time-dependent networks ⋮ An approximation algorithm for a general class of parametric optimization problems ⋮ Analysis of FPTASes for the multi-objective shortest path problem ⋮ Shadows of Newton polytopes ⋮ Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint ⋮ Approximation schemes for the parametric knapsack problem ⋮ An approximation algorithm for a general class of multi-parametric optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matching theory
- Matching is as easy as matrix inversion
- An application of simultaneous diophantine approximation in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Specified precision polynomial root isolation is in NC
- Probabilistic parallel prefix computation
- Complexity of some parametric integer and network programming problems
- A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
- An O(n2log n) parallel max-flow algorithm
- Fast Parallel Matrix Inversion Algorithms
- An $\NC$ Algorithm for Minimum Cuts
This page was built for publication: A lower bound for the shortest path problem