Multi-Source Spanning Tree Problems
Arthur Farley, Paraskevi Fragopoulou, David Krumme, Andrzej Proskurowski, Dana Richards
Committee:
Technical Report(Dec 1969)
Keywords:

We consider a model of communication in a network, where multiple sources have messages to disseminate among the network membership. We propose that all the messages (one from each source) be disseminated along the same spanning tree of the network and consider the problem of constructing such a tree. One evaluative measure for suitability of the construction is the sum of distances from each source for each vertex. We show that finding the exact solution in this case is NP-hard, for any selection of the sources. We therefore investigate this problem for some restricted classes of graphs and give efficient solution algorithms for those. We also consider alternative measures of goodness of spanning communication trees.