Algorithms for dense graphs and networks

We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size $\lambda$ a maximal matching in an $n$--vertex bipartite graph in time $O(n^{2} + n^{2.5}/\lambda) = 0(n^{2.5}/\log n)$, how to compute the transitive closure of a digraph with $n$ vertices and $m$ edges in time $0(nm/\lambda)$, how to solve the uncapacitated transportation problem with integer costs in the range $[0..C]$ and integer demands in the range $[-U..U]$ in time $0((n^3(\log\log n/\log n)^{1/2} + n^2 \log U)\log nC)$, and how to solve the assignment problem with integer costs in the range $[0..C]$ in time $0(n^{2.5}\log nC/(\log n/\log \log n)^{1/4})$. \\ Assuming a suitably compressed input, we also show how to do depth--first and breadth--first search and how to compute strongly connected components and biconnected components in time $0(n\lambda + n^2/\lambda)$, and how to solve the single source shortest path problem with integer costs in the range $[0..C]$ in time $0(n^2(\log C)/\log n)$