Laporkan Masalah

ALGORITMA FILTER-KRUSKAL SEBAGAI SALAH SATU SOLUSI MINIMUM SPANNING TREE

AHMAD ZAKKY, Dr. Adhitya Ronnie Effendie M.Sc

2016 | Skripsi | S1 MATEMATIKA

Filter-Kruskal adalah sebuah modifikasi sederhana dari Algoritma Kruskal yang menghindari pengelompokan edge yang sesungguhnya tidak perlu pada MST (Minimum Spanning Tree). Untuk sebarang graf dengan nilai sebarang, Filter Kruskal berjalan pada waktu O(m + n log n log m/n) , dengan kata lain waktu pengerjaan dari algoritma adalah linear untuk graf yang tidak terlalu tipis (jumlah m edge mendekati jumlah n vertex) . Pada percobaan diindikasikan bahwa Algoritma tersebut (Filter-Kruskal) mempunyai hasil yang sangat bagus untuk keseluruhan range pada edge yang rapat.

Filter-Kruskal is a simple modifcation of Kruskal's Algorithm that avoids sorting edges that are obviously not in the MST. For arbitrary graph with random edge wights Filter-Kruskal runs in time O(m + n log n log m/n), i.e. in linear time for not too prase graphs. Experiments indicate that the algorithm has very good practical performance over the entire range of edge densities.

Kata Kunci : FIlter Kruskal Algorithm

  1. S1-2016-269575-abstract.pdf  
  2. S1-2016-269575-bibliography.pdf  
  3. S1-2016-269575-tableofcontent.pdf  
  4. S1-2016-269575-title.pdf