Max‐min partitioning of grid graphs into connected components

Journal Article

  • Author(s): Ronald Becker, Isabella Lari, Mario Lucertini, Bruno Simeone
  • Article first published online: 07 Dec 1998
  • DOI: 10.1002/(SICI)1097-0037(199809)32:2<115::AID-NET4>3.0.CO;2-E
  • Read on Online Library
  • Subscribe to Journal


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. © 1998 John Wiley & Sons, Inc. Networks 32: 115–125, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.