Title : ( The Cost Constraint Minimum Spanning Tree and the label constrained minimum spanning tree problems )
Authors: Zahra Naji Azimi , Majid Salari , Bruce Golden , Raghu S. Raghavan , Paolo Toth ,
Free PreviewAccess to full-text not allowed by authors
Abstract
Given an undirected graph whose edges are labeled or colored and have weights, and a budget B, the goal of the Cost Constrained Minimum Label Spanning Tree Problem(CCMLST) is to nd a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. In the Label Constrained Minimum Spanning Tree Problem(LCMST), we are given a threshold K on the number of labels. The goal is to nd a minimum weight spanning tree that uses at most K distinct labels. In this paper, we present a Variable Neighborhood Search algorithm for the CCMLST and LCMST problems.
Keywords
, Cost Constraint Minimum Spanning Tree, label constrained minimum spanning tree, heuristics
@inproceedings{paperid:1024982,
author = {Naji Azimi, Zahra and Salari, Majid and Bruce Golden and Raghu S. Raghavan and Paolo Toth},
title = {The Cost Constraint Minimum Spanning Tree and the label constrained minimum spanning tree problems},
booktitle = {23rd Euro Conference on Operational Research},
year = {2009},
location = {Bonn, GERMANY},
keywords = {Cost Constraint Minimum Spanning Tree; label constrained minimum spanning tree; heuristics},
}
%0 Conference Proceedings
%T The Cost Constraint Minimum Spanning Tree and the label constrained minimum spanning tree problems
%A Naji Azimi, Zahra
%A Salari, Majid
%A Bruce Golden
%A Raghu S. Raghavan
%A Paolo Toth
%J 23rd Euro Conference on Operational Research
%D 2009
