zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A mixed integer linear formulation for the minimum label spanning tree problem. (English) Zbl 1162.90575
Summary: We deal with the minimum label spanning tree problem. This is a relevant problem with applications such as telecommunication networks or electric networks, where each edge is assigned with a label (such as a color) and it is intended to determine a spanning tree with the minimum number of different labels. We introduce some mixed integer formulations for this problem and prove that one of their relaxations always gives the optimal value. Finally we present and discuss the results of computational experiments.

90C35Programming involving graphs or networks
90C11Mixed integer programming
90B10Network models, deterministic (optimization)
Full Text: DOI
[1] Cerulli, R.; Fink, A.; Gentili, M.; Voss, S.: Metaheuristics comparison for the minimum labelling spanning tree problem, The next wave on computing, optimization, and decision technologies 29, 93-106 (2005)
[2] Chang, R. S.; Leu, S. -J.: The minimum labeling spanning trees, Information processing letters 63, No. 5, 277-282 (1997) · Zbl 0938.90063 · doi:10.1016/S0020-0190(97)00127-0
[3] Consoli S, Moreno JA, Mladenović N, Darby-Dowman K. Constructive heuristics for the minimum labelling spanning tree problem: a preliminary comparison. Technical Report DEIOC-4, Universidad de La Laguna, La Laguna, September 2006 \langle http://hdl.handle.net/2438/504\rangle .
[4] Krumke, S.; Wirth, H.: On the minimum label spanning tree problem, Information processing letters 66, No. 2, 81-85 (1998) · Zbl 0938.90064 · doi:10.1016/S0020-0190(98)00034-9
[5] Kruskal, J. B.: On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American mathematical society 7, 48-50 (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[6] Prim, R. C.: Shortest connection networks and some generalizations, Bell system technical journal 36, 1389-1401 (1957)
[7] Wan, Y.; Chen, G.; Xu, Y.: A note on the minimum label spanning tree, Information processing letters 84, No. 2, 99-101 (2002) · Zbl 1042.68055 · doi:10.1016/S0020-0190(02)00230-2
[8] Xiong Y. The minimum labeling spanning tree problem and some variants. PhD thesis, Graduate School of the University of Maryland, USA, 2005.
[9] Xiong, Y.; Golden, B.; Wasil, E.: Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem, Operations research letters 33, No. 1, 77-80 (2005) · Zbl 1076.90050 · doi:10.1016/j.orl.2004.03.004
[10] Xiong, Y.; Golden, B.; Wasil, E.; Chen, S.: The label-constrained minimum spanning tree problem, Telecommunications modeling, policy, and technology. Operations research/computer science interfaces 44, 39-58 (2008)