Premium
Heuristics for the strong generalized minimum label spanning tree problem
Author(s) -
Cerrone Carmine,
D'Ambrosio Ciriaco,
Raiconi Andrea
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21882
Subject(s) - spanning tree , minimum spanning tree , heuristics , heuristic , enhanced data rates for gsm evolution , computer science , mathematical optimization , gomory–hu tree , mathematics , tree (set theory) , euclidean minimum spanning tree , kruskal's algorithm , steiner tree problem , algorithm , combinatorics , artificial intelligence , tree structure , k ary tree , binary tree
In this work we introduce and study the strong generalized minimum label spanning tree (GMLST), a novel optimization problem defined on edge‐labeled graphs. Given a label set associated to each edge of the input graph, the aim is to look for the spanning tree using the minimum number of labels. Differently from the previously introduced GMLST problem, including a given edge in the solution means that all its labels are used. We present a mathematical formulation, as well as three heuristic approaches to solve the problem. Computational results compare the performances of the proposed algorithms.