Solving The Degree Constrained Minimum Spanning Tree Problem Using Tabu And Modified Penalty Search Methods  

Oleh:

Wamiliana

Jenis: Article from Journal - ilmiah nasional - terakreditasi DIKTI - non-atma jaya
Dalam koleksi: Jurnal Teknik Industri vol. 6 no. 1 (Jun. 2004), page 1-9.
Topik: minimum spanning tree; tabu search; degree constrained.
Fulltext: 1.pdf (48.68KB)

Isi artikel

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 nonnegative), 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.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali