# 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},`

`}`