DESAIN DAN ANALISIS ALGORITMA KOMPUTASI JUMLAH BRIDGE PADA GRAF DINAMIS INKREMENTAL

TSAQOVA, YUSRO (2016) DESAIN DAN ANALISIS ALGORITMA KOMPUTASI JUMLAH BRIDGE PADA GRAF DINAMIS INKREMENTAL. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

[img] Text
5112100095-Undergraduate_Theses.pdf
Restricted to Repository staff only

Download (3MB)

Abstract

Komputasi jumlah bridge pada graf dinamis inkremental merupakan permasalahan perhitungan jumlah bridge pada sebuah graf yang bentuknya berubah secara dinamis karena pertambahan edge. Untuk mendapatkan jumlah bridge pada graf bisa dilakukan dengan komputasi ulang untuk setiap operasi penambahan edge namun pendekatan tersebut tentunya tidak efisien. Pada Tugas Akhir ini akan dirancang penyelesaian permasalahan di atas dengan melihat beberapa kondisi yang harus diperhatikan dari pasangan vertex yang mengalami pertambahan edge yaitu apakah pasangan vertex berada dalam himpunan connectedcomponent yang berbeda, himpunan connected-component yang sama namun dalam himpunan bridge-block yang berbeda atau dalam himpunan bridge-block yang sama. Implementasi dari solusi ini menggunakan bantuan struktur data disjoint set ditambah pendekatan heuristik union by weight dan path compression. Hasil dari Tugas Akhir ini telah berhasil menyelesaikan permasalahan di atas dengan cukup efisien dengan kompleksitas waktu O(M(α(N))) dimana α(N) adalah invers dari fast-growing ackermann function dan bernilai ≤ 4 untuk setiap N. ====================================================================================================== Bridge number computation on incremental graph is a problem of computation of bridge number on a graph which is dynamically changed because of edge addition. For obtaining bridge total number in a graph, the use of re-computation for every single operation of edge addition is possible, but certainly it is inefficient. This undergraduate thesis will design the problem solving of the problem above by seeing some conditions which should be considered from vertex pair which has edge addition, which is whether vertex are located in same connected-component set or not but in a same bridge-block set or in similar bridge-block set. The implementation of this solution is using the help of disjoint set data structure and heuristic union by weight and path compression. The result of this undergraduate thesis has successfully solved the problem mentioned with sufficient enough by the O(M(α(N))) time complexity where α(N) is the inverse of fast-growing ackermann function and has less than or equal 4 for every single N.

Item Type: Thesis (Undergraduate)
Uncontrolled Keywords: Graf, Bridge, Online, Pencarian, Dinamis, Inkrementa
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
T Technology > T Technology (General)
Divisions: Faculty of Information Technology > Informatics Engineering > (S1) Undergraduate Theses
Depositing User: Mr. Fandika aqsa
Date Deposited: 10 Jan 2017 02:39
Last Modified: 10 Jan 2017 02:39
URI: http://repository.its.ac.id/id/eprint/1422

Actions (login required)

View Item View Item