On the complexity of an optimal routing tree problem

A routing tree for a set of tasks is a decision tree which assigns the tasks to their destinations according to the features of the tasks. A weighted routing tree is one with costs attached to each link of the tree. Links of the same feature have the same cost. It is proved that the problem of finding a routing tree of the minimum cost for a given set of tasks of two features is NP-complete.This research was supported in part by theNSF grantsDCR-8501226 andDCR-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 Department of Mathematics, University of California, Santa Barbara, California.