MPI-I-91-114
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)$.
-
- Attachement: MPI-I-91-114.pdf (12286 KBytes)
URL to this document: https://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},
}