Item

Abstract

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)$.