Max-min partitioning of grid graphs into connected components
✍ Scribed by Becker, Ronald; Lari, Isabella; Lucertini, Mario; Simeone, Bruno
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 197 KB
- Volume
- 32
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
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.