The complexity of minimizing certain cost metrics for \(k\)-source spanning trees. (English) Zbl 1073.68061
Summary: We investigate multisource spanning tree problems where, given a graph with edge weights and a subset of the nodes defined as sources, the object is to find a spanning tree of the graph that minimizes some distance-related cost metric. This problem can be used to model multicasting in a network where messages are sent from a fixed collection of senders and communication takes place along the edges of a single spanning tree. For a limited set of possible cost metrics of such a spanning tree, we either prove the problem is NP-hard or we demonstrate the existence of an efficient algorithm to find an optimal tree.
References:
| [1] | E. Dahlhaus, P. Dankelmann, W. Goddard, H.C. Swart, MAD trees and distance hereditary graphs, in: Proceedings of JIM’2000, Metz, France, 2000, pp. 49-54.; E. Dahlhaus, P. Dankelmann, W. Goddard, H.C. Swart, MAD trees and distance hereditary graphs, in: Proceedings of JIM’2000, Metz, France, 2000, pp. 49-54. · Zbl 1022.05023 |
| [2] | Farley, A. M.; Fragopoulou, P.; Krumme, D.; Proskurowski, A.; Richards, D., Multi-source spanning tree problems, J. Interconnection Networks, 1, 1, 61-71 (2000) |
| [3] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York, NY · Zbl 0411.68039 |
| [4] | Hu, T. C., Optimum communication spanning trees, SIAM J. Comput., 3, 3, 188-195 (1974) · Zbl 0269.90010 |
| [5] | Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H.G., The complexity of the network design problem, Networks, 8, 4, 279-285 (1978) · Zbl 0395.94048 |
| [6] | Krumme, D. W.; Fragopoulou, P., Minimum eccentricity multicast trees, Discrete Mathematics and Theoretical Computer Science, 4, 157-172 (2001) · Zbl 0981.68118 |
| [7] | B. McMahan, A. Proskurowski, Multi-source spanning trees: algorithms for minimizing source eccentricities, Discrete Applied Mathematics, submitted for publication.; B. McMahan, A. Proskurowski, Multi-source spanning trees: algorithms for minimizing source eccentricities, Discrete Applied Mathematics, submitted for publication. · Zbl 1062.68090 |
| [8] | Ravi, R.; Sundaram, R.; Marathe, M. V.; Rosenkrantz, D. J.; Ravi, S. S., Spanning trees—short or small, SIAM J. Discrete Math., 9, 2, 178-200 (1996) · Zbl 0855.05058 |
| [9] | Wu, B. Y.; Chao, K.; Tang, C. Y., Approximation algorithms for some optimum communication spanning tree problems, Discrete Appl. Math., 102, 245-266 (2000) · Zbl 0957.68088 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
