Tech Report CS-91-07

Parallel Graph-Embedding and the Mob Heuristic

John E. Savage and Markus G. Wloka

February 1991


We show that important local search heuristics for grid and hypercube embeddings based on the successive swapping of pairs of vertices, such as simulated annealing, are P-hard and unlikely to run in polylogarithmic time. This puts experimental results reported in the literature into perspective: attempts to construct the exact parallel equivalent of serial simulated-annealing-based heuristics for graph embedding have yielded disappointing parallel speedups.

We have developed and implemented on the Connection Machine CM-2 a new massively parallel heuristic for such embeddings, called the Mob heuristic. We report on an extensive series of experiments with our heuristics on the 32K-processor CM-2 Connection Machine for grid and hypercube embeddings that show impressive reductions in edge costs and run in less than 30 minutes on random graphs of 1 million edges. Due to excessive run times, previous heuristics reported in the literature were able to construct graph embeddings only for graphs that were 100 to 1000 times smaller than those used in our experiments.

(complete text in pdf)