Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms (1997)
Shiva Chaudhuri, Christos D. Zaroliagis
We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered....
Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms (1997)
Shiva Chaudhuri, Christos D. Zaroliagis
We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered....
All-Pairs Min-Cut in Sparse Networks (1997)
Srinivasa R. Arikati, Shiva Chaudhuri, Christos D. Zaroliagis
Algorithms are presented for the all-pairs min-cut problem in bounded tree-width, planar and sparse networks. The approach used is to preprocess the input n-vertex network so that, afterwards, the...
All-Pairs Min-Cut in Sparse Networks (1997)
Srinivasa R. Arikati, Shiva Chaudhuri, Christos D. Zaroliagis
. Algorithms for the all-pairs min-cut problem in bounded tree-width and sparse networks are presented. The approach used is to preprocess the input network so that, afterwards, the value of a...
The Randomized Complexity of Maintaining the Minimum (1996)
Shiva Chaudhuri, Gerth Stlting Brodal, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms (1996)
Shiva Chaudhuri, Christos D. Zaroliagis
We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered....
Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms (1996)
Shiva Chaudhuri, Christos D. Zaroliagis
We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered....
Tight Bounds on Oblivious Chaining (1996)
The chaining problem is defined as follows. Given values a 1 ; :::; an ; a i = 0 or 1, 1 i n, compute b 1 ; :::; b n , such that b i = maxfj j a j = 1; j ! ig. (Define maxfg = 0) The chaining problem...
All-Pairs Min-Cut in Sparse Networks (1996)
Srinivasa R. Arikati, Shiva Chaudhuri, Christos D. Zaroliagis
Algorithms are presented for the all-pairs min-cut problem in bounded tree-width, planar and sparse networks. The approach used is to preprocess the input n-vertex network so that, afterwards, the...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stlting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
All-Pairs Min-Cut in Sparse Networks (1996)
Srinivasa R. Arikati, Shiva Chaudhuri, Christos D. Zaroliagis
Algorithms are presented for the all-pairs min-cut problem in bounded tree-width, planar and sparse networks. The approach used is to preprocess the input n-vertex network so that, afterwards, the...
Deterministic Restrictions in Circuit Complexity (1996)
Shiva Chaudhuri, Jaikumar Radhakrishnan
We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S 1Gammaffl(d) )...
Shortest Paths in Digraphs of Small Treewidth. Part II: Optimal Parallel Algorithms (1995)
Shiva Chaudhuri, Christos D. Zaroliagis
We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered....
Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms (1995)
Shiva Chaudhuri, Christos D. Zaroliagis
We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered....
Prefix Graphs and Their Applications (1995)
Shiva Chaudhuri, Torben Hagerup
. The range product problem is, for a given set S equipped with an associative operator ffi, to preprocess a sequence a1 ; : : : ; an of elements from S so as to enable efficient subsequent...