SOLVING THE DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM USING TABU AND MODIFIED PENALTY SEARCH METHODS
:
https://doi.org/10.9744/jti.6.1.1-9
Keywords:
minimum spanning tree, tabu search, degree constrained.Abstract
In this paper we consider the Degree Constrained Minimum Spanning Tree Problem. This problem is concerned with finding, in a given edge weighted graph G (all weights are non-negative), the minimum weight spanning tree T satisfying specified degree restrictions on the vertices. This problem arises naturally in communication networks where the degree of a vertex represents the number of line interfaces available at a center. Because of its NP-completeness, a number of heuristics have been proposed. In this paper we propose two new search methods: one based on the method of Tabu search and the other based on a penalty function approach. For comparative analysis, we test our methods on some benchmark problems. The computational results support our methods.Downloads
Published
How to Cite
Issue
Section
License
Articles published in the Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri will be Open-Access articles distributed under the terms and conditions of the Creative Commons Attribution License (CC BY).
This work is licensed under a Creative Commons Attribution License (CC BY).