標題: Optimality of consecutive and nested tree partitions
作者: Chang, GJ
Hwang, FK
應用數學系
Department of Applied Mathematics
公開日期: 1-九月-1997
摘要: 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
期刊: NETWORKS
Volume: 30
Issue: 2
起始頁: 75
結束頁: 80
顯示於類別:期刊論文


文件中的檔案:

  1. A1997XR26500001.pdf