Tech Report CS-93-01

Mob --- A Parallel Heuristic for Graph-Embedding

John E. Savage and Markus G. Wloka

January 1993

Abstract:

We have extended the {\em Mob}\ heuristic for graph partitioning to grid and hypercube embedding and have efficiently implemented our new heuristic on the CM-2 Connection Machine. We have conducted an extensive series of experiments to show that it exploits parallelism, is fast, and gives very low embedding costs. For example, on the 32K-processor CM-2 it runs in less than 30 minutes on random graphs of 1 million edges and shows impressive reductions in edge costs. Due to excessive run times, other heuristics reported in the literature can only construct graph embeddings for graphs that are 100 to 1000 times smaller than those used in our experiments.

(complete text in pdf or gzipped postscript)