Skip to Main content Skip to Navigation
Book sections

A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem

Abstract : Given a connected, undirected and m-partite complete graph G=(V1∪V2∪...∪Vm;E), the Generalized Minimum Spanning Tree Problem (GMSTP) consists in finding a tree with exactly m−1 edges, connecting the m clusters V1,V2,...,Vm through the selection of a unique vertex in each cluster. GMSTP finds applications in network design, irrigation agriculture, smart cities, data science, among others. This paper presents a new multigraph mathematical formulation for GMSTP which is compared to existing formulations from the literature. The proposed model proves optimality for well-known GMSTP instances. In addition, this work opens new directions for future research to the development of sophisticated cutting plane and decomposition algorithms for related problems.
Complete list of metadatas
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 10:00:58 AM
Last modification on : Thursday, February 13, 2020 - 5:37:10 PM





Ernando Gomes de Sousa, Rafael Castro de Andrade, Andréa Cynthia Santos. A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem. ISCO 2018: Combinatorial Optimization, 10856, Springer, pp.133-143, 2018, Lecture Notes in Computer Science, ⟨10.1007/978-3-319-96151-4_12⟩. ⟨hal-02291657⟩



Record views