article no. SS971493 Faster Shortest-Path Algorithms for Planar Graphs (2008)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
A randomized parallel algorithm for single-source shortest paths (1997)
Philip N. Klein, Sairam Subramanian
Abstract We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest path problem can be efficiently reduced to solving a...
A randomized parallel algorithm for single-source shortest paths (1997)
Philip N. Klein, Sairam Subramanian
We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest path problem can be efficiently reduced to solving a series of...
Parallel and dynamic shortest-path algorithms for sparse graphs /--by Sairam Subramanian. (1995)
Available in film copy from University Microfilms International.
An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs (1995)
Sairam Subramanian, Sairam Subramanian, Roberto Tamassia, Roberto Tamassia, Jeffrey Scott Vitter, Jeffrey Scott Vitter
Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the...
Parallel and Dynamic Shortest-Path Algorithms for Sparse Graphs (1995)
Sairam Subramanian, Sairam Subramanian, Philip N. Klein, Roberto Tamassia, Jeffrey S. Vitter
ere capable of anything and instilling in us a desire to be the best in whatever we did. I would also like to thank my high school teachers Mr. Jaypal Chandra and Ms. Bhuvaneshvari for showing me...
Path Caching: A Technique for Optimal External Searching (1994)
Sridhar Ramaswamy, Sridhar Ramaswamy, Sairam Subramanian, Sairam Subramanian
) Sridhar Ramaswamy Brown University sr@cs.brown.edu Sairam Subramanian y Brown University ss@cs.brown.edu Abstract External 2-dimensional searching is a fundamental problem with many applications in...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Philip Klein Brown, Satish Rao, Monika Rauch, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edgelengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Sairam Subramanian, Philip Klein, Philip Klein, Satish Rao, Satish Rao, Monika Rauch, ...
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edgelengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Complexity Models for Incremental Computation (1994)
Peter Bro, Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia
We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...
Complexity Models for Incremental Computation (1994)
Peter B. Miltersen, Jeffresy S. Vitter, Peter Bro Miltersen, Sairam Subramanian, Sairam Subramanian, Jeffrey Scott Vitter, ...
We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...
A Linear-Processor Polylog-Time Algorithm for Shortest Paths in Planar Graphs (1993)
Philip N. Klein, Philip N. Klein, Sairam Subramanian, Sairam Subramanian
We give an algorithm requiring polylog time and a linear number of processors to solve singlesource shortest paths in directed planar graphs, bounded-genus graphs, and 2-dimensional overlap graphs....
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs (1993)
Philip N. Klein, Sairam Subramanian
In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter ffl such that 0 ! ffl, our algorithm maintains...
An E cient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs (1993)
Sairam Subramanian, Roberto Tamassia, Jeffrey Scott Vitter, Sairam Subramanian, Roberto Tamassia
Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the...
ARTICLE NO. AL970888 A Randomized Parallel Algorithm for Single-Source Shortest Paths* (1991)
Philip N. Klein, Sairam Subramanian
We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of...