Max-min partitioning of grid graphs into connected components
Ronald I. Becker, Isabella Lari, Mario Lucertini
1998
Citations
15
Citations
Journal
Networks
Full text
Semantic Scholar
Key Takeaway Key Takeaway: The max-min partitioning of grid graphs into connected components is NP-hard for rectangles with at least three rows, but a shifting algorithm approximates the optimal solution and allows for error estimates and asymptotic error estimates.
Abstract
The partitioning of a rectangular grid graph with weighted vertices into p connected components such that the component of smallest weight is as heavy as possible (the max-min problem) is considered. It is shown 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 hypotheses. A further shifting algorithm is also given which allows for error estimates under a priori hypotheses and for asymptotic error estimates. 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 algorithm and is dealt with in another paper.