MAX-MIN PARTITIONING OF GRID GRAPHS INTO CONNECTED COMPONENTS

The partitioning of a rectangular grid graph with weighted vertices in to p connected components such that the component of smallest weight i s as heavy as possible (the max-min problem) is considered. It is show n that the problem is NP-hard for rectangles with at least three rows. A shifting algorithm is given which approximates the optimal solution . Bounds for the relative error are determined under a posteriori hypo theses. A further shifting algorithm is also given which allows for er ror estimates under a priori hypotheses and for asymptotic error estim ates. A similar approach can be taken with the problem of finding the partition whose largest component is as small as possible (the min-max problem). The case of rectangles with two rows has a polynomial algor ithm and is dealt with in another paper. (C) 1998 John Wiley & Sons, I nc.