A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem - Archive ouverte HAL Access content directly
Book Sections Year : 2018

A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem

(1) , (2) , (3)
1
2
3

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.
Not file

Dates and versions

hal-02291657 , version 1 (19-09-2019)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
43 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More