ABSTRAK
Nama : Muhammad Ayaz Dzulfikar
Program Studi : Computer Science
Judul : Pendekatan Dynamic Programming pada GPU Untuk Algoritma
Fixed-Parameterized dari Maximum Independent Set
pada Graf dengan Treewidth Rendah
Pembimbing : Lim Yohanes Stefanus, Ph.D
Dr. Johannes K. Fichte
Independent set dari sebuah graf adalah sebuah subhimpunan dari verteks yang tidak terdapat
edge di antara dua vertex, sedangkan maximum independent set adalah independent
set dengan kardinalitas maksimum. Banyak permasalahan yang dapat dimodelkan
menjadi permasalahan maximum independent set. Salah satu cara untuk menyelesaikan
permasalahan ini adalah dengan menggunakan fixed-parameterized algorithm. Telah ditunjukkan
bahwa maximum independent set itu fixed-parameterized tractable apabila diparameterisasi
dengan treewidth, namun belum ada yang membuat penerapannya. Dalam
skripsi ini, dibuatlah penerapan dari teori tersebut. Beberapa implementasi dibuat, dan
didesain untuk dieksekusi secara serial di CPU atau secara paralel dengan bantuan GPU.
Hasil dari eksperimen menunjukkan bahwa eksekusi secara paralel dapat lebih lambat,
namun secara umum dapat mengungguli eksekusi secara serial.
Kata kunci:
Dynamic programming, fixed-parameterized algorithm, GPU, maximum independent set,
treewidth
viii
|
|