ALCOMFT-TR-01-89

Robert Elsässer, Thomas Lücking and Burkhard Monien
New Spectral Bounds on k-Partitioning of Graphs
Paderborn. Work package 2. May 2001.

Abstract: When executing processes on parallel computer systems they encounter as a major bottleneck inter-processor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of (|V|)/(2k)\sum_i=1^klambda_i for the k-section width of a graph is well-known. We show new relations between the structure and the eigenvalues of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define some global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor.

Postscript file: ALCOMFT-TR-01-89.ps.gz (130 kb).