A polynomial-time algorithm for max-min partitioning of ladders

Citation
R. Becker et al., A polynomial-time algorithm for max-min partitioning of ladders, THEOR C SYS, 34(4), 2001, pp. 353-374
Citations number
10
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORY OF COMPUTING SYSTEMS
ISSN journal
1432-4350 → ACNP
Volume
34
Issue
4
Year of publication
2001
Pages
353 - 374
Database
ISI
SICI code
1432-4350(200107/08)34:4<353:APAFMP>2.0.ZU;2-F
Abstract
Given a grid graph with two rows, an arbitrary number N of columns (briefly , a ladder) and a weight function defined on its vertex set V, one wants to partition V into a given number p of connected components, so as to maximi ze the smallest weight of a component. We present an O (N(4)p max{p, log N} )-time algorithm, which combines dynamic programming with pre-processing an d search techniques. An 0 (N) -time algorithm for the case p = 2 is also gi ven. In a companion paper [2] we show that the problem for a grid graph with thr ee rows is NP-hard, and we give approximate algorithms for grid graphs with an arbitrary number of rows.