NPAC Technical Report SCCS-652
Parallel Incremental Graph Partitioning
Chao-Wei Ou, Sanjay Ranka
Submitted August 2 1994
Abstract
Partitioning graphs into equally large groups of nodes while
minimizing the number of edges between different groups
is an extremely important problem in parallel computing.
For instance, efficiently parallelizing
several scientific and engineering applications requires the partitioning
of data or tasks among processors such that the computational load on each
node is roughly the same, while communication is minimized.
Obtaining exact solutions is computationally intractable,
since graph-partitioning is an NP-complete.
For a large class of irregular and adaptive data parallel applications
(such as adaptive meshes), the computational structure changes from one
phase
to another in an incremental fashion. In incremental graph-partitioning
problems the partitioning of the graph needs to be updated as the graph
changes over time; a small number of nodes or edges may be added or deleted
at any given instant.
In this paper we use a linear programming-based method to solve the
incremental graph partitioning problem. All the steps used by our method
are inherently parallel and hence our approach can be easily
parallelized. By using an initial solution for the graph partitions derived
from recursive spectral bisection-based methods, our
methods can achieve repartitioning at considerably lower cost than can be
obtained by applying recursive spectral bisection from scratch.
Further, the quality of the partitioning
achieved is comparable to that achieved by applying recursive
spectral bisection to the incremental graphs from scratch.