MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Algorithms for dense graphs and networks

Cheriyan, Joseph and Mehlhorn, Kurt

September 1991, 29 pages.

Status: available - back from printing

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

  • MPI-I-91-114.pdf
  • Attachement: MPI-I-91-114.pdf (12286 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Cheriyan, Joseph and Mehlhorn, Kurt},
  TITLE = {Algorithms for dense graphs and networks},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-114},
  MONTH = {September},
  YEAR = {1991},
  ISSN = {0946-011X},