Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Algorithms for dense graphs and networks

Cheriyan, Joseph and Mehlhorn, Kurt

MPI-I-91-114. September 1991, 29 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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)$.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-91-114.pdf12286 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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},