GRID-GRAPH PARTITIONING
William W. Donaldson · 2000
Previous researchers showed that striping techniques produced very good (and, in some cases, asymptotically optimal) partitions when applied to grid graphs. These striping algorithms can be thought of as two-phase methods. The first phase consists of breaking the original problem into smaller, but similar, problems (striping). The second phase (stripe assignment) consists of the actual assignment of cells within the stripes. Results from this reseach show how to improve both phases. We improve the stripe-assignment phase of Christou, Meyer and Yackel so as to guarantee locally optimal solutions for rectangular grid graphs. It is shown that under certain assumptions, the assignment algorithm of Christou-Meyer will produce a locally optimal solution. This algorithm is extended to handle a larger class of grid graphs. A third algorithm is described that produces a locally optimal solution for the same class of problems and also potentially reduces the chance of producing solutions with c...