Tree Partitioning under Constraints -- Clustering for Vehicle Routing Problems

Hamacher, Anja and Hochstättler, Winfried and Moll, Christoph (2000) Tree Partitioning under Constraints -- Clustering for Vehicle Routing Problems.
Published in: Discrete Applied Mathematics Vol. 99 (1-3). pp. 55-69.

Abstract

We present a dynamic programming algorithm for the following problem: Given a tree T=(V,E), a set of q non-negative integer weights wi:V -> N on the nodes, and a threshold Ri, i=1,...,q. Partition the vertices of the tree into connected components T0,..., Tk, such that for all i in {1,...,q}, j in {0,...,k} sum_{v in Tj} wi(v) <= Ri and k is minimal. We show that this problem is hard, if q is unbounded or if T has unbounded maximum degree. In all other cases the running time of the dynamic program has a polynomial worst-case bound.


Actions:
Download: [img] Postscript - Preprinted Version
Download (333kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-283
Depositing User: Winfried Hochstättler
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 13:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/283