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.
Document type :
Book sections
Complete list of metadatas
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 10:00:58 AM
Last modification on : Wednesday, June 24, 2020 - 10:50:14 AM





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