Analisis dan Implementasi Algoritma Finding Maximum Independent Set (FMIS) Untuk Mencari Maximum Independent Set Pada Graf

Arifin Suhendar

Informasi Umum

Kode

113071135

Klasifikasi

005.1 - Computer programming

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Informatika Teori Dan Pemrograman

Dilihat

359 kali

Informasi Lainnya

Abstraksi

ABSTRAKSI: Pencarian Maximum Independent Set (MIS) pada sebuah graf adalah salah satu permasalahan NP-Complete. Maximum Independent Set (MIS) pada sebuah graf memiliki penerapan yang penting dan diperlukan algoritma yang tepat untuk mencarinya. Permasalahan yang terdapat pada algoritma yang ada sekarang adalah kompleksitas waktu eksekusi yang masih cenderung berkembang secara eksponensial. Sebuah algoritma bernama Finding Maximum Independent Set (FMIS) diajukan oleh Ahmad Sharieh dkk pada tahun 2008 untuk mencari MIS pada graf. Algoritma ini mampu menemukan MIS dengan kompleksitas waktu eksekusi O(n4) untuk graf dengan n simpul. Algoritma FMIS diimplementasikan dan dicoba pada graf tidak berarah dan tidak berbobot dengan variasi ukuran dan kepadatan berbeda. Selanjutnya, algoritma tersebut dianalisis untuk melihat efisiensinya dengan parameter speed, dan space savings. Hasilnya menunjukkan bahwa dilihat dari segi kompleksitas waktu, algoritma FMIS lebih efisien dibandingkan algoritma lain untuk mencari MIS. Algoritma ini memberikan hasil keluaran yang benar dan waktu eksekusi algoritma FMIS sangat dipengaruhi oleh ukuran graf dan density dari graf.Kata Kunci : np-complete, maximum independent set, graf, fmisABSTRACT: Searching for a Maximum Independent Set (MIS) in a graph is one of the NP-Complete problem. The Maximum Independent Set (MIS) in a graph has important applications and needs exact algorithm to find it. The problems found in the existing algorithms are that the execution time complexity of the available exact algorithms to find the MIS tend to be an exponential growth function. An algorithm called Finding Maximum Independent Set (FMIS) has been proposed by Ahmad Shariehin 2008 to find MIS of a graph. The algorithm is able to find the MIS with execution time complexity O(n4) for a graph with n vertices. FMIS algorithm was implemented and tested on an undirected graph with different sizes and densities. Later it will be analyzed to see the efficiency of the algorithm with speed, and space savings parameters. The results show that in terms of time complexity, FMIS algorithm is more efficient than other algorithms to find the MIS. This algorithm gives the correct output and FMIS algorithm execution time is influenced by the size of the graph and the density of the graph.Keyword: np-complete, maximum independent set, graph, fmis.