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