Algoritma untuk Degree Constrained Minimum Spanning Tree
| Main Author: | Butarbutar, Nurlinda Sari |
|---|---|
| Other Authors: | Suwilo, Saib, Harahap, Marwan |
| Format: | Student Papers |
| Bahasa: | ind |
| Subjects: | |
| Online Access: |
http://repository.usu.ac.id/handle/123456789/31036 |
Daftar Isi:
- 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.
- 060803011