We present a reformulation of the 2n+o(n) lower bound of Bent and John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 213--216] for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart from giving a more intuitive proof for the lower bound, the new formulation opens up possibilities for improving it. We use the new formulation to show that any pair-forming median finding algorithm, i.e., a median finding algorithm that starts by comparing $\lfloor n/2\rfloor$ disjoint pairs of elements must perform, in the worst case, at least 2.01 n + o(n) comparisons. This provides strong evidence that selecting the median requires at least cn+o(n) comparisons for some c> 2.

Improving a long standing result of Bent and John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, RI, 1985, pp. 213--216], and extending a recent result of Dor, Håstad, Ulfberg, and Zwick [ SIAM J. Discrete Math., 14 (2001), pp. 299--311], we obtain a $(2{+}\epsilon)n$ lower bound (for some fixed $\epsilon>0$) on the number of comparisons required, in the worst case, for selecting the median of n elements.

Improving a long-standing result of Schönhage, Paterson, and Pippenger [ J. Comput. System Sci., 13 (1976), pp. 184--199] we show that the median of a set containing n elements can always be found using at most $c \cdot n$ comparisons, where c

An H-decomposition of a graph G=(V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition. In 1980, Holyer conjectured that H-decomposition is NP-complete whenever H is connected and has three edges or more. Some partial results have been obtained since then. A complete proof of Holyer's conjecture is the content of this paper. The characterization problem of all graphs H for which H-decomposition is NP-complete is hence reduced to graphs where every connected component contains at most two edges.

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 et al. [SIAM J. Comput., 28 (1999), pp. 1167--1181], we describe an $\Ot(\min\{n^{3/2}m^{1/2},n^{7/3}\})$-time algorithm APASP 2 for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP 2 is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k>2, we describe an ${\tilde{O}}(\min\{n^{2-{2}/{(k+2)}}m^{{2}/{(k+2)}}, n^{2+{2}/{(3k-2)}}\})$-time algorithm APASP k for computing all distances in G with an additive one-sided error of at most k. We also give an ${\tilde{O}}(n^2)$-time algorithm ${\bf APASP}_\infty$ for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in ${\tilde{O}}(n^2)$ time. We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every $u,v\in V$ we have $\delta_G(u,v)\le \delta_F(u,v)\le \delta_G(u,v)+k$. We show that every unweighted graph on n vertices has a 2-emulator with ${\tilde{O}}(n^{3/2})$ edges and a 4-emulator with ${\tilde{O}}(n^{4/3})$ edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with ${\tilde{O}}(n^{3/2})$ edges and that such a 3-spanner can be built in ${\tilde{O}}(mn^{1/2})$ time. We also describe an ${\tilde{O}}(n(m^{2/3}+n))$-time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.

Improving a long standing result of Bent and John (1985), we obtain a (2+/spl epsiv/)n lower bound (for some fixed /spl epsiv/>0) on the number of comparisons required, in the worst case, for selecting the median of n elements. The new lower bound is obtained using a weight function that allows us to combine leaf counting and adversary arguments.

An H-decomposition of a graph G = (V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition.