TSAQOVA, YUSRO (2016) DESAIN DAN ANALISIS ALGORITMA KOMPUTASI JUMLAH BRIDGE PADA GRAF DINAMIS INKREMENTAL. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5112100095-Undergraduate_Theses.pdf Download (3MB) | Preview |
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. EDP T Technology > T Technology (General) |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Mr. Fandika aqsa |
| Date Deposited: | 10 Jan 2017 02:39 |
| Last Modified: | 27 Dec 2018 07:55 |
| URI: | http://repository.its.ac.id/id/eprint/1422 |
Actions (login required)
 |
View Item |