The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances

Petrică C. Pop

European Journal of Operational Research, 2020, vol. 283, issue 1, 1-15

Abstract: In this paper, some of the main known results relative to the generalized minimum spanning tree problem are surveyed. The principal feature of this problem is related to the fact that the vertices of the graph are partitioned into a certain number of clusters and we are interested in finding a minimum-cost tree spanning a subset of vertices with precisely one vertex considered from every cluster. The paper is structured around the following main headings: problem definition, variations and practical applications, complexity aspects, integer programming formulations, exact and heuristic solution approaches developed for solving this problem. Furthermore, we also discuss some open problems and possible research directions.

Keywords: Combinatorial optimization; Generalized minimum spanning tree problem; Survey (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719304217
Full text for ScienceDirect subscribers only

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:eee:ejores:v:283:y:2020:i:1:p:1-15

DOI: 10.1016/j.ejor.2019.05.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().