|
USU Institutional Repository »
Student Papers (SP) »
Mathematics and Natural Sciences »
SP - Mathematics »
Please use this identifier to cite or link to this item:
http://repository.usu.ac.id/handle/123456789/31036
|
| Title: | Algoritma untuk Degree Constrained Minimum Spanning Tree |
| Authors: | Butarbutar, Nurlinda Sari |
| Advisors: | Suwilo, Saib
Harahap, Marwan |
| Issue Date: | 9-Feb-2012 |
| 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. |
| Abstract (other language): | Permasalahan Degree Constrained Minimum Spanning Tree (DCMST) pada graph
G(V,E) berbobot terhubung tak berarah merupakan permasalahan untuk menemukan
spanning tree T di G dengan total panjang edge yang minimum dan degree
dari setiap verteks vi di T dibatasi oleh bi dimana dT (vi) bi. Untuk menyelesaikan
permasalahan degree constrained minimum spanning tree dilakukan dengan
memodifikasi algoritma Kruskal, dimana sebuah edge diterima di T, jika edge
tidak membentuk cycle pada edge terdahulu yang berada di T dan verteks-verteks
ujungnya memenuhi batas maksimum degree yang diberikan, yaitu dT (vj) bj
dan dT (vk) bk. |
| Keywords: | Degree Constrained Minimum Spanning Tree
Algoritma |
| URI: | http://repository.usu.ac.id/handle/123456789/31036 |
| Appears in Collections: | SP - Mathematics
|
Items in USU-IR are protected by copyright, with all rights reserved, unless otherwise indicated.
|
|
