Performance oriented spanning trees

Spanning trees have been widely used for routing in various areas, like computer networks, operations research, VLSI, and etc. They are used to connect n points together so that the total interconnection length is minimum. This paper studies a new form of spanning tree, known as the performance directed spanning tree. It shows that this problem is NP-hard and provide a heuristic for it. Experiments are conducted on randomly generated graphs and the results reported.