# 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.

Download: |
Postscript
- Preprinted Version
Download (333kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |