%A W.W. Donaldson and Robert R. Meyer
%T A Dynamic-Programming Heuristic for Regular Grid-Graph Partitioning
%D December 2000
%R 00-06
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
Previous researchers have demonstrated that striping heuristics
produce
very good (and, in some cases, asymptotically optimal)
partitions for regular grid graphs. These earlier methods differed
in the domains of application and the stripe-height selection process,
and did not have polynomial run-time guarantees.
In this paper, we transform the stripe selection problem for general
grid graphs into
a shortest path problem. The running time for the entire process
of transforming the problem and solving for the shortest path is polynomial
with
respect to the length of input for the original problem.
Computational results are presented that demonstrate improved solution
quality for general domains.