A lower bound for the shortest path problem

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Proceedings 15th Annual IEEE Conference on Computational Complexity

• Publication date

  2000-07-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CCC.2000.856731
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lower Bounds in a Parallel Model without Bit Operations

  1999influential reference
• An NC Algorithm for Minimum Cuts

  1997cited by this paper
• Limits to Parallel Computation: P-Completeness Theory

  1995influential reference
• Synthesis of Parallel Algorithms

  1993cited by this paper
• Book Review: Introduction to Parallel Algorithms and Architectures : Arrays, Trees, Hypercubes by F. T. Leighton (Morgan Kauffman Pub, 1992)

  1992cited by this paper
• Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes

  1991cited by this paper
• Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes

  1991cited by this paper
• Specified precision polynomial root isolation is in NC

  1990cited by this paper
• Lower bounds for algebraic computation trees with integer inputs

  1989cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988cited by this paper
• An application of simultaneous diophantine approximation in combinatorial optimization

  1987cited by this paper
• Matching is as easy as matrix inversion

  1987cited by this paper
• Annals of Discrete Mathematics

  1986cited by this paper
• Almost optimal lower bounds for small depth circuits

  1986cited by this paper
• A fast parallel algorithm for determining all roots of a polynomial with real roots

  1986cited by this paper
• A new approach to the maximum flow problem

  1986cited by this paper
• Matching Theory (North-Holland mathematics studies)

  1986cited by this paper
• The complexity of some problems in parametric linear and combinatorial programming

  1983influential reference
• Lower bounds for algebraic computation trees

  1983cited by this paper
• Complexity of some parametric integer and network programming problems

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• An O(n² log n) Parallel MAX-FLOW Algorithm

  1982cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Fast parallel matrix inversion algorithms

  1975cited by this paper

• A survey of exact and approximation algorithms for linear-parametric optimization problems

  2025cites this paper
• DNCs Require More Planning Steps

  2024cites this paper
• Ripple spreading algorithm: a new method for solving multi-objective shortest path problems with mixed time windows

  2023influential citation
• A Novel All-Pairs Shortest Path Algorithm ∗

  2023cites this paper
• Combinatorial Contracts Beyond Gross Substitutes

  2023influential citation
• DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs

  2022cites this paper
• Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint

  2022cites this paper
• An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions

  2022cites this paper
• Generalized Parametric Path Problems

  2021cites this paper
• An approximation algorithm for a general class of multi-parametric optimization problems

  2021cites this paper
• Shadows of newton polytopes

  2021influential citation
• A novel graph matrix representation: sequence of neighbourhood matrices with an application

  2020cites this paper
• An approximation algorithm for a general class of parametric optimization problems

  2020cites this paper
• An FPTAS for a General Class of Parametric Optimization Problems

  2019cites this paper
• Parametric Shortest Paths in Planar Graphs

  2018influential citation
• Finding Extreme Supported Solutions to the Bi-Objective Shortest Path Problem

  2017cites this paper
• An FPTAS for the parametric knapsack problem

  2017cites this paper
• A Survey of Shortest-Path Algorithms

  2017cites this paper
• An FPTAS for the Knapsack Problem with Parametric Weights

  2017cites this paper
• Approximation schemes for the parametric knapsack problem

  2017cites this paper
• Network pricing problem with unit toll

  2017cites this paper
• Analysis of FPTASes for the multi-objective shortest path problem

  2016cites this paper
• Distributionally Robust Optimization of Two‐Stage Lot‐Sizing Problems

  2016cites this paper
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles

  2015cites this paper
• Mathematical programming approaches to pricing problems

  2015cites this paper
• Permissive multi-strategies in timed games ∗

  2014cites this paper
• Distance Oracles for Time-Dependent Networks

  2013cites this paper
• Approximation of Multiobjective Optimization Problems

  2011cites this paper
• On the Complexity of Time-Dependent Shortest Paths

  2011influential citation
• Maximum flows and parametric shortest paths in planar graphs

  2010cites this paper
• Multi-Objective Model Checking of Markov Decision Processes

  2007cites this paper
• Stochastic Shortest Paths Via Quasi-convex Maximization

  2006cites this paper
• [Delta]-stepping: a parallelizable shortest path algorithm

  2003cites this paper
• Design and analysis of sequential and parallel single-source shortest-paths algorithms

  2002cites this paper
• Approximation of Multiobjective Optimization Problems

  2001cites this paper
• ∆-stepping : a parallelizable shortest path algorithm

  year unknowncites this paper