Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Dorit Dor:

TR97-040 | 17th September 1997
Dorit Dor, Shay Halperin, Uri Zwick

All Pairs Almost Shortest Paths

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

TR95-031 | 25th June 1995
Dorit Dor, Uri Zwick

Selecting the median

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

ISSN 1433-8092 | Imprint