max planck institut
informatik

# MPI-I-91-114

## 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)$.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
12286 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: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-114
BibTeX
@TECHREPORT{CheriyanMehlhorn91,
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},
}