All reports by Author Uri Zwick:

__
TR00-060
| 17th August 2000
__

Uri Zwick#### All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

__
TR97-040
| 17th September 1997
__

Dorit Dor, Shay Halperin, Uri Zwick#### All Pairs Almost Shortest Paths

__
TR95-040
| 26th July 1995
__

Uri Zwick, Michael S. Paterson#### The complexity of mean payoff games on graphs

__
TR95-031
| 25th June 1995
__

Dorit Dor, Uri Zwick#### Selecting the median

__
TR94-009
| 12th December 1994
__

Noga Alon, Raphael Yuster, Uri Zwick#### Color-coding

Uri Zwick

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 >>>

Dorit Dor, Shay Halperin, Uri Zwick

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 >>>

Uri Zwick, Michael S. Paterson

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 >>>

Dorit Dor, Uri Zwick

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 >>>

Noga Alon, Raphael Yuster, Uri Zwick

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 >>>