Title: Optimality of consecutive and nested tree partitions
Authors: Chang, GJ
Hwang, FK
Department of Applied Mathematics
Issue Date: 1-Sep-1997
Abstract: We consider the problem of partitioning the vertex-set of a tree to p parts to minimize a cost function. Since the number of partitions is exponential in the number of vertices, it is helpful to identify small classes of partitions which also contain optimal partitions. Two such classes, called consecutive partitions and nested partitions, have been well studied for the set partition problem, which is a special case of the tree-partition problem when the tree is a path. We give conditions on the optimality of these classes on tree partitions and also extend our results to tree networks. (C) 1997 John Wiley & Sons, Inc.
URI: http://hdl.handle.net/11536/335
ISSN: 0028-3045
Volume: 30
Issue: 2
Begin Page: 75
End Page: 80
Appears in Collections:Articles

Files in This Item:

  1. A1997XR26500001.pdf