PENGGUNAAN ALGORITMA SOLLIN YANG DIMODIFIKASI UNTUK MENYELESAIKAN MASALAH DEGREE CONSTRAINED MINIMUM SPANNING TREE
| Main Author: | FEBI MUDIYANTO , 1617031100 |
|---|---|
| Format: | Bachelors NonPeerReviewed Book Report |
| Terbitan: |
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
, 2020
|
| Subjects: | |
| Online Access: |
http://digilib.unila.ac.id/60973/1/ABSTRAK.pdf http://digilib.unila.ac.id/60973/2/SKRIPSI%20FULL.pdf http://digilib.unila.ac.id/60973/3/SKRIPSI%20TANPA%20BAB%20PEMBAHASAN.pdf http://digilib.unila.ac.id/60973/ |
Daftar Isi:
- Diberikan graf terhubung berbobot G (V, E), Degree Constrained Minimum Spanning Tree (DCMST) adalah masalah untuk menentukan spanning tree T dari G dengan bobot minimum dan juga tetap mempertahankan persyaratan derajat pada tiap titik. Dalam penelitian ini, algoritma untuk menyelesaikan DCMST dibuat berdasarkan modifikasi Algoritma Sollin. Algoritma ini diimplementasikan menggunakan 300 masalah. Hasil penelitian menunjukkan bahwa kinerja algoritma adalah 8.33% bedanya dari batas bawah DCMST. Kata Kunci : minimum spanning tree, degree constrained minimum spanning tree, modified Sollin. ABSTRACT Given a connected weighted graph G(V,E), The Degree Constrained Minimum Spanning Tree (DCMST) is a problem of finding a spanning tree T of G with the minimum weight while also maintaining the degree requirement on every vertex. In this research, the algorithm for solving the DCMST is made based on Sollin’s algorithm. The algorithm is implemented using 300 random table problems and the result show that the performance of the algorithm against its lower bound is 8,33%. Key words : minimum spanning tree, degree constrained minimum spanning tree, modified Sollin.