Seminar Tugas Akhir

Ribut Setiadi
G05400042

Teknik Local-Ratio untuk Masalah Feedback Arc Set pada Graf Berarah Terboboti

Ribut Setiadi. Tidak Local_Ratio untuk Masalah Feedback Arc Set pada Graf Berarah Terboboti. Dibimbing Oleh Fahren Bukhari dan Farida Hanum. Suatu digraf atau graf berarah adalah pasangan terurut V dan A; dengan V adalah himpunan takkosong dan berhingga yang anggotanya disebut simpul, dan A adalah pasangan terurut elemen taksama dari V. Setiap elemen di A disebut sisi berarah. Pada tulisan ini dibahas suatu algoritme yang berdasarkan pada teknik local-Ratio untuk menentukan feedback arc set (FAS) minimum. Masalah feedback arc set minimum adalah menentukan himpunan sisi-sisi berarah brebobot minimum sedemikian sehingga jika himpunan tersebut dihilangkan akan membuat digraf menjadi acyclic. Teknik local-ratio menggunakan strategi dengan mengurangi bobot dan penyelesaikan masalah dengan bobot yang lebih sederhana. Dengan demikian jika terdapat suatu cyle pada digraf dengan bobot minimum pada salah satu sisi berarah pada cycle, maka algoritme FAS akan mengurangi semua bobot sisi berarah pada cycle tersebut dengan e, dan bobot sisi berarah minimum akan dihilangkan dari graf dan akan dimasukkan ke FAS. Algoritme FAS ini berjalan dalam Worst-case running time O(m(m+n)) pada digraf dengan n simpul dan m sisi, dan aproksimasi FAS dalam rasio yang dibatasi panjang cycle terpanjang digraf.