Abstract
Given a positive integer K and a connected, undirected graph G whose edges are labeled (or colored) and have weights, the label-constrained minimum spanning tree (LCMST) problem seeks a minimum weight spanning tree with at most K distinct labels (or colors). In this paper, we prove that the LCMST problem is NP-complete. Next, we introduce two local search methods to solve the problem. Then, we present a genetic algorithm which gets comparable results, but is much faster. In addition, we present two mixed integer programming for-mulations for the LCMST problem. We compare these on some small problem instances. Finally, we introduce a dual problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
P.M. Camerini, F. Maffinoli, S. Martello, and P. Toth. Most and least uniform spanning tree. Discrete Appl. Math, 15:181–197, 1986.
R.-S. Chang and S.-J. Leu. The minimum labeling spanning trees. Inform. Process. Lett., 63(5):277–282, 1997.
D. Eppstein. Finding the k smallest spanning trees. BIT, 32:237–248, 1992.
Z. Galil and B. Schieber. On finding most uniform spanning trees. Discrete Appl. Math., 20:173–175, 1988.
J.-H. Ho, D.T. Lee, C.-H. Chang, and C.K.Wong. Minimum diameter spanning trees and related problems. SIAM J. Comput., 20:987–997, 1991.
S.O. Krumke and H.-C. Wirth. On the minimum label spanning tree problem. Inform. Process. Lett., 66(2):81–85, 1998.
X. Shen and W. Liang. A parallel algorithm for multiple edge updates of minimum spanning trees. Proc. 7th Internet. Parallel Processing Symp., pages 310–317, 1993.
Y. Wan, G. Chen, and Y. Xu. A note on the minimum label spanning tree. Inform. Process. Lett., 84:99–101, 2002.
Y. Xiong, B. Golden, and E. Wasil. A one-parameter genetic algorithm for the minimum labeling spanning tree problem. IEEE Transactions on Evolutionary Computation, 9(1):55–60, 2005.
Y. Xiong, B. Golden, and E. Wasil. Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem. Operations Research Lett., 33(1):77–80, 2005.
Y. Xiong, B. Golden, and E. Wasil. Improved heuristics for the minimum label spanning tree problem. IEEE Transactions on Evolutionary Computation, 10(6):700–703, 2006.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Xiongm, Y., Golden, B., Wasil, E., Chen, S. (2008). The Label-Constrained Minimum Spanning Tree Problem. In: Raghavan, S., Golden, B., Wasil, E. (eds) Telecommunications Modeling, Policy, and Technology. Operations Research/Computer Science Interfaces, vol 44. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-77780-1_3
Download citation
DOI: https://doi.org/10.1007/978-0-387-77780-1_3
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-77779-5
Online ISBN: 978-0-387-77780-1
eBook Packages: Computer ScienceComputer Science (R0)