Skripsi

Analisis kinerja algoritma dinitz / Bahrul Ulum

Abstrak
ABSTRAK Ulum Bahrul. 2010. Analisis Kinerja Algoritma Dinitz. Skripsi Jurusan Matematika FMIPA Universitas Negeri Malang. Pembimbing (I) Dra. Sapti Wahyuningsih M.Si (II) Dra. Susy Kuspambudi Andaini M. Kom. Kata kunci maximum flow kinerja algoritma Dinitz running time Masalah maximum flow adalah salah satu kajian dalam teori graph yang mempunyai banyak aplikasi dalam kehidupan sehari-hari. Penyelesaian masalah maximum flow akan menjadi lebih mudah dan efektif jika menggunakan algoritma. Banyak algoritma yang ditawarkan untuk menyelesaikan masalah maximum flow seperti algoritma Preflow-push algoritma Pelabelan Aka algoritma Dijkstra dan algoritma Ford-Fulkerson. Banyaknya algoritma penyelesaian masalah tersebut menyebabkan ketepatan pemilihan algoritma sangat diperlukan. Alternatif penyelesaian masalah maximum flow selalu dicari untuk mendapatkan solusi yang optimum tetapi dengan cara yang efektif. Akibatnya diperlukan analisis dari algoritma penyelesaikan masalah maximum flow untuk menilai kinerja dan keefektifannya sehingga diperoleh situasi yang tepat kapan algoritma tersebut unggul untuk digunakan. Salah satu algoritma yang dapat dijadikan alternatif adalah algoritma Dinitz. Algoritma Dinitz menggunakan pencarian shortest augmenting path sebagai dasar penyelesaian maximum flow problem. Algoritma ini menggunakan dua algoritma lain yaitu algoritma konstruksi layered network dan algoritma blocking flow. Algoritma Dinitz dimulai dari pengkonstruksian residual network dan dilanjutkan pembentukan layered network. Proses diteruskan dengan mencari blocking flow pada layered network dan mengupdatenya pada netwok asal. Iterasi berhenti ketika tidak ada lagi lintasan dari source ke sink pada residual network. Dengan menggunakan layered network pencarian lintasan dari source ke sink memerlukan waktu eksekusi atau running time sebesar O(). Algoritma Dinitz mengalami paling banyak -1 fase perulangan. Untuk menyelesaikan maximum flow problem dengan menggunakan algoritma Dinitz dibutuhkan running time sebesar O(2). Nilai running time ini secara umum lebih baik daripada nilai running time pada Algoritma Ford-Fulkerson. Keunggulan lain algoritma ini dibandingkan algoritma Ford-Fulkerson adalah banyak iterasi pada algoritma ini tidak bergantung pada pemilihan lintasan selain itu algoritma Dinitz lebih unggul dalam menyelesaikan maximum flow problem pada network yang mempunyai sisi berkapasitas irasional. Namun algoritma Dinitz memiliki kekurangan yaitu algoritma ini kurang efektif digunakan pada network yang seluruh lintasannya merupakan edge disjoint st-path dengan panjang berbeda.

Informasi Detail

DDC

Rs 518.2 ULU a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2010.

Deskripsi Fisik

x, 105 lembar : il., tab. ; 30 cm.

Bahasa

Indonesia

No Reg

01862/KI/10

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2010

Subjek

1. ALGORITMA DINITZ

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. SUSY KUSPAMBUDI ANDAINI

Lampiran Berkas