SOLVING THE DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM USING TABU AND MODIFIED PENALTY SEARCH METHODS
:
https://doi.org/10.9744/jti.6.1.1-9Keywords:
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
2005-04-28
How to Cite
[1]
W. Wamiliana, “SOLVING THE DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM USING TABU AND MODIFIED PENALTY SEARCH METHODS”, Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri, vol. 6, no. 1, pp. 1-9, Apr. 2005.
Issue
Section
Articles
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).