Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

 
Data Skripsi
 
Judul : Teknik Local-Ratio untuk Masalah Feedback Arc Set pada Graf Berarah Terboboti
Jenis : Skripsi
Penulis : Ribut Setiadi
NRP : G05400042
Tanggal Lulus : 28 August 2007
Tanggal Seminar : 10 July 2007 11:00
Tanggal Sidang : 17 July 2007 11:00
Pembimbing : Dr. Ir. Fahren Bukhari, M.Sc.
Dra. Farida Hanum, M.Si.
Ringkasan : 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.

Random Quotes

Kepercayaan adalah satu-satunya faktor terpenting, baik dalam hubungan pribadi maupun profesional.

anonim