AbstractWe show that the shortest path problem cannot be solved in o(logn) time on an unbounded fan-in PRAM without bit operations using poly(n) processors, even when the bit-lengths of the weights on the edges are restricted to be of size O(log3n). This shows that the matrix-based repeated squaring algorithm for the shortest path problem is optimal in the unbounded fan-in PRAM model without bit operations
The lirst result presented in this paper is a lower bound of Q(log n) for the computation time of co...
This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighte...
The single source shortest path (SSSP) problem lacks parallel solutions which are fast and simultane...
AbstractWe show that the shortest path problem cannot be solved in o(logn) time on an unbounded fan-...
We show that the shortest path problem cannot be solved in o(log n) time on an unbounded fan-in PRAM...
We define a natural and realistic model of parallel computation called the PRAM model without bit op...
We present the first $m\,\text{polylog}(n)$ work, $\text{polylog}(n)$ time algorithm in the PRAM mod...
AbstractAn N × N matrix product can be evaluated with precision E > 0 in O(Ns+ϵ log (M/E) log log (M...
This paper presents a new semantic method for proving lower bounds in computational complexity. We u...
AbstractWe consider the problem of preprocessing an n-vertex digraph with real edge weights so that ...
textThe shortest path and minimum spanning tree problems are two of the classic textbook problems i...
We show that it is not possible to speed-up the Knapsack problem efficiently in the parallel algebra...
AbstractThe first result presented in this paper is a lower bound of Ω(log n) for the computation ti...
We introduce a variant of the Shortest Path Problem (SPP), in which we impose additional constraints...
We design a faster algorithm for the all-pairs shortest path problem under the conventional RAM mod...
The lirst result presented in this paper is a lower bound of Q(log n) for the computation time of co...
This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighte...
The single source shortest path (SSSP) problem lacks parallel solutions which are fast and simultane...
AbstractWe show that the shortest path problem cannot be solved in o(logn) time on an unbounded fan-...
We show that the shortest path problem cannot be solved in o(log n) time on an unbounded fan-in PRAM...
We define a natural and realistic model of parallel computation called the PRAM model without bit op...
We present the first $m\,\text{polylog}(n)$ work, $\text{polylog}(n)$ time algorithm in the PRAM mod...
AbstractAn N × N matrix product can be evaluated with precision E > 0 in O(Ns+ϵ log (M/E) log log (M...
This paper presents a new semantic method for proving lower bounds in computational complexity. We u...
AbstractWe consider the problem of preprocessing an n-vertex digraph with real edge weights so that ...
textThe shortest path and minimum spanning tree problems are two of the classic textbook problems i...
We show that it is not possible to speed-up the Knapsack problem efficiently in the parallel algebra...
AbstractThe first result presented in this paper is a lower bound of Ω(log n) for the computation ti...
We introduce a variant of the Shortest Path Problem (SPP), in which we impose additional constraints...
We design a faster algorithm for the all-pairs shortest path problem under the conventional RAM mod...
The lirst result presented in this paper is a lower bound of Q(log n) for the computation time of co...
This paper is about the problem of finding a shortest s-t path using at most h edges in edge-weighte...
The single source shortest path (SSSP) problem lacks parallel solutions which are fast and simultane...
DOI
Add to ORKG