| 0N THE COMPLEXITY OF AN OPTIMAL ROUTING TREE PROBLEM |
| |
| 作者姓名： | 堵丁柱 KER-IKo |
| |
| 作者单位： | Institute of Applied Mathematics，Academia Sinica，State University of New York at Stony Brook，U.S.A. |
| |
| 基金项目： | This research was supported in part by the NSF grants DCB-8501226 and DCR-8696135. Part of this work was done while the first author was at the Mathematical Sciences Research Institute, Berkeley, California, and while the second author was at the Departm |
| |
| 摘 要： | A routing tree for a set of tasks is a decision tree which assigns the tasks to their destinationsaccording to the features of the tasks. A weighted routing tree is one with costs attached to each linkof the tree. Links of the same feature have the same cost. It is proved that the problem of finding ?routing tree of the minimum cost for a given set of tasks of two features is NP-complete.
|
| 本文献已被 CNKI 等数据库收录！ |
