A polyhedral approach to the generalized minimum labeling spanning tree problem

Thiago Gouveia da Silva (), Serigne Gueye, Philippe Michelon, Luiz Satoru Ochi and Lucídio dos Anjos Formiga Cabral
Additional contact information
Thiago Gouveia da Silva: IFPB, Instituto Federal de Educação, Ciência e Tecnologia da Paraíba
Serigne Gueye: Université d’Avignon
Philippe Michelon: Université d’Avignon
Luiz Satoru Ochi: UFF, Universidade Federal Fluminense
Lucídio dos Anjos Formiga Cabral: UFPB, Universidade Federal da Paraíba

EURO Journal on Computational Optimization, 2019, vol. 7, issue 1, No 3, 47-77

Abstract: Abstract The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple graph G, in which each edge has one label, by using a minimum number of labels. It is an NP-hard problem that was introduced by Chang and Leu (Inf Process Lett 63(5):277–282, 1997. https://doi.org/10.1016/S0020-0190(97)00127-0 ). Chen et al. (Comparison of heuristics for solving the gmlst problem, in: Raghavan, Golden, Wasil (eds) Telecommunications modeling, policy, and technology, Springer, Boston, pp 191–217, 2008) subsequently proposed a generalization of the MLSTP, called the generalized minimum labeling spanning tree problem (GMLSTP), that allows a situation in which multiple labels can be assigned to an edge. Here, we show how the GMLSTP can be expressed as an MLSTP in a multigraph. Both problems have applications in various areas such as computer network design, multimodal transportation network design, and data compression. We propose a new compact binary integer programming model to solve exactly the GMLSTP and analyze the polytope associated with the formulation. The paper introduces new concepts, gives the polytope dimension, and describes five new facet families. The polyhedral comparison results for the studied polytope show that the new model is theoretically superior to current state-of-the-art formulations.

Keywords: Polyhedral study; Facets; Edge-labeled graph; Spanning tree; 90C27; 90C10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13675-018-0099-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:7:y:2019:i:1:d:10.1007_s13675-018-0099-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-018-0099-5

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().