We present two new algorithms for solving the {\em All Pairs Shortest Paths\/} (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in $\Ot(n^{2+\mu})$ ... more >>>

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth, Chekuri and Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time ... more >>>

We study the complexity of finding the values and optimal strategies of MEAN PAYOFF GAMES on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski and considered by Gurvich, Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm for the solution of such games, the decision problem ... more >>>

Improving a long standing result of Sch\"{o}nhage, Paterson and Pippenger we show that the MEDIAN of a set containing n elements can always be found using at most 2.95n comparisons. This is the full version of the paper. An extended abstract version of the paper apperead in the proceedings SODA'95. more >>>

We describe a novel randomized method, the method of {\em color-coding\/} for finding simple paths and cycles of a specified length $k$, and other small subgraphs, within a given graph $G=(V,E)$. The randomized algorithms obtained using this method can be derandomized using families of {\em perfect hash functions\/}. Using the ... more >>>