Massive Multi-digraphs

modeled as dynamic weighted multi-digraphs. Their sizes range from tens of
gigabytes to terabytes. The sheer volume of these graphs brings with it an
interesting series of computational and visualization challenges.

We will discuss external memory algorithms for connectivity, minimum
spanning trees and maximal matchings together with heuristics
for quasiclique finding and diameter computations. From the visualization
store we will describe an external memory hierarchy that allow us to
use computer graphics techniques like dynamic visibility to provide
navigation control. We will present experimental results with graphs
having on the order of 200 million vertices and we will point
out some mathematical problems that have surfaced along the way.

(some of this work has been done in cooperation with A. Buschbaum, S. Krishnan,
P. Pardalos, M. Resende, S. Sudarsky, A. Ucko and J. Westbrook)