Muhammad, Nuril (2026) PERFORMA ALGORITMA ITERATED GREEDY DALAM MENYELESAIKAN PERMASALAHAN HIMPUNAN k-DOMINASI PADA GRAF REGULER. Undergraduate thesis, Universitas Diponegoro.

	Text Bagian 1 - Nuril Muhammad.pdf Download (425kB)
	Text Bagian 2 - Nuril Muhammad.pdf Restricted to Repository staff only Download (1MB) | Request a copy
	Text Bagian 3 - Nuril Muhammad.pdf Download (93kB)

Abstract

Permasalahan himpunan k-dominasi pada graf, suatu generalisasi dari masalah klasik himpunan dominasi. Permasalahan ini bersifat NP-hard sehingga menuntut pendekatan heuristik yang efektif terutama untuk instans berukuran besar. Penelitian ini menganalisis performa algoritma Iterated Greedy (IG) dalam menyelesaikan masalah himpunan k-dominasi pada graf reguler. Algoritma IG yang dikembangkan menggabungkan tiga fase utama: konstruksi awal melalui greedy berbasis kelengkapan, destruksi dengan fraksi titik tertentu, dan rekonstruksi greedy. Performa IG dievaluasi melalui simulasi numerik pada graf d-reguler acak untuk parameter k bernilai 2, 3, 4, dan 5, dengan derajat d dari 3 hingga 100. IG dibandingkan dengan dua algoritma baseline: Simple Greedy dan Probabilistic Construction. Hasil eksperimen menunjukkan bahwa IG secara konsisten menghasilkan rasio kardinalitas terhadap orde graf yang lebih kecil dibandingkan kedua baseline, dengan perbaikan signifikan untuk semua nilai k yang diuji.. Pola diminishing increments teramati saat k bertambah, mengindikasikan struktur permasalahan berubah secara kontinyu seiring peningkatan kebutuhan redundansi. Kontribusi penelitian ini meliputi formulasi formal masalah pada graf reguler dengan beberapa teorema struktural, adaptasi IG yang lengkap dan dapat direproduksi, serta tinjauan empiris komprehensif pada rentang parameter yang luas dan belum pernah dilaporkan secara sistematis sebelumnya.

Kata kunci: algoritma Iterated Greedy, himpunan k-dominasi, graf reguler.

Actions (login required)

View Item