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

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