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

Karya Ilmiah Alumni
Previous month Previous day Next day Next month
See by year See by month See by week See Today Search Jump to month
Sidang Tugas Akhir Ribut Setiadi
Selasa, Juli 17 2007, 11:00 - 12:00 by  Alamat e-mail ini dilindungi dari spambot, anda harus memampukan JavaScript untuk melihatnya Hits : 2549

Sidang Tugas Akhir

Ribut Setiadi
G05400042

Dosen Pembimbing

Ir. Fahren Bukhari, M.Sc.
Dra. Farida Hanum, M.Si.

Dosen Penguji Dr. Ir. Sri Nurdiati, M.Sc.

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.

Back

JEvents v1.4.2   Copyright © 2006-2007

Random Quotes

Lepas dari perusahaan apa tempat anda bekerja, jangan pernah lupa bahwa produk terpenting yang anda jual adalah diri anda sendiri.

anonim