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 ... 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 ... 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 ... 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\/}. ... more >>>