A lower bound for the shortest path problem

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

zbMATH Keywords

shortest path problemrepeated squaring algorithm

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

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