Heuristics for the strong generalized minimum label spanning tree problem

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. Diff...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2019-09, Vol.74 (2), p.148-160
Main Authors: Cerrone, Carmine, D'Ambrosio, Ciriaco, Raiconi, Andrea
Format: Article
Language:English
Subjects:
Algorithms
carousel greedy
Ethernet
generalized problem
Graph theory
Labels
minimum label spanning tree
Optimization
pilot method
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21882