Algoritma untuk Degree Constrained Minimum Spanning Tree

Abstract

The Degree Constrained Minimum Spanning Tree (DCMST) on undirected weighted connected graph G(V,E) is a problem to find a spanning tree T in G with whose total edge length is minimal and the degree of each vertex vi in T at most a given value bi where dT (vi) bi. For solving this problem, we modified Kruskal algorithm, an edge received in T, if an edge did not produce any cycle with preceding edge in T and a both endpoints should not exceed some given maximum degrees that dT (vj) bj and dT (vk) bk.