Desain dan Analisis Algoritma Dekomposisi Graf menjadi Block-Cut Tree untuk Pencarian Path pada Studi Kasus SPOJ STOPCITY Stopping-Off Cities

Zahara, Pristi (2022) Desain dan Analisis Algoritma Dekomposisi Graf menjadi Block-Cut Tree untuk Pencarian Path pada Studi Kasus SPOJ STOPCITY Stopping-Off Cities. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111740000112-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2024. Download (3MB) | Request a copy

Abstract

Aplikasi dari teori graph sangat luas dan dipakai dalam berbagai disiplin ilmu maupun dalam kehidupan sehari hari. Contoh persoalan yang dapat dimodelkan menggunakan teori graph diantaranya masalah dalam jaringan komputer, transportasi, riset operasi, dan lain sebagainya. Tugas akhir ini membahas sebuah permasalahan pada situs SPOJ dengan kode soal STOPCITY bernama "Stopping-Off Cities" yang dapat dimodelkan dengan graph. Dalam permasalahan tersebut, didefinisikan sebuah stopping-off city atau kota pemberhentian sebagai kota yang menjadi bagian dari setidaknya satu kemungkinan tour antara kota asal A dan kota tujuan B di sebuah negara, di mana tour merupakan urutan kota-kota yang dikunjungi di sebuah perjalanan. Seorang tour operator memiliki misi untuk mendapatkan seluruh stopping-off city antara kota A dan kota B. Sebuah negara dapat dimodelkan sebagai sebuah undirected graph, sehingga permasalahan yang dibahas menjadi pencarian sekumpulan vertex dari seluruh kemungkinan path antara dua node di sebuah graph. Untuk menyelesaikan permasalahan secara efisien, digunakan konsep bikonektivitas dengan menggunakan struktur data block-cut tree, yaitu tree yang terdiri atas block-block biconnected component yang berkaitan dengan satu sama lain melalui cut vertex atau articulation point dari sebuah graph. Block-cut tree dari sebuah graph bisa didapatkan dengan waktu eksekusi linear, karena seluruh articulation point dan biconnected component dapat diidentifikasi menggunakan algoritma depth-first search (DFS) dari Robert Tarjan. Dari hasil uji coba yang dilakukan, implementasi algoritma dekomposisi atau penyederhanaan graph menjadi block-cut tree dapat menyelesaikan permasalahan secara efisien, dengan waktu eksekusi yang konstan yaitu 0.04 detik dan penggunaan memori yang konstan yaitu 5.4 MB.
================================================================================================
Applications of graph theory has been widely used in many disciplines as well as daily life. There are some examples of problems that can be modeled using graph theory, such as computer networking, transportation, research operation, etc. This thesis discussed a problem on SPOJ website with STOPCITY as the problem code named "Stopping-Off Cities" that can be modeled as a graph. The problem is described as follows. A stopping-off city is defined as a city that is part of at least one possible tour between a departure city A and a destination city B in a country, where a tour is a sequence of cities that are visited during a trip. A tour operator has a mission to select all possible stopping-off cities between a city A and a city B. A country can be modeled as an undirected graph, hence the discussed problem is about finding a set of vertices from all possible paths between two nodes in a graph. To solve the problem efficiently, biconnectivity concept is utilized using block-cut tree data structure, which is a tree consists of biconnected component blocks connected to each other with a cut vertex or an articulation point. A block-cut of a graph can be obtained in linear time, since all the articulation points and biconnected components can be identified using Robert Tarjan's depth-first search (DFS) algorithm. From the test results, the algorithm implementation of graph decomposition into block-cut tree can solve the problem efficiently, with constant execution time which is 0.04 seconds and constant memory usage which is 5.4 MB.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	bikonektivitas, block-cut tree, dekomposisi graph, depth-first search, graph, pencarian path, biconnectivity, graph decomposition, pathfinding
Subjects:	Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) T Technology > T Technology (General) > T11 Technical writing. Scientific Writing T Technology > T Technology (General) > T58.8 Productivity. Efficiency
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Pristi Zahara
Date Deposited:	28 Jan 2022 01:33
Last Modified:	28 Jan 2022 01:33
URI:	http://repository.its.ac.id/id/eprint/92469

Actions (login required)

View Item