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.

Creator(s)

• WAMILIANA

Contributor(s)

-

Publisher

Universitas Kristen Petra; 2004

Language

English

Category

jou – Journal

Sub Category

-

Source

Jurnal Teknik Industri Vol. 6, No. 1, Juni 2004: 1 - 9; Wamiliana (NA00000393)

Subject(s)

-

File(s)

• jiunkpe-ns-jou-2004-na00000393-7418-spanning_tree-resource1.pdf