Authors

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.