Desain Dan Analisis Penggunaan Teknik Square-Root Decomposition Pada Penyelesaian Permasalahan Spoj 12803 - Graph

Affan, Muhamad (2022) Desain Dan Analisis Penggunaan Teknik Square-Root Decomposition Pada Penyelesaian Permasalahan Spoj 12803 - Graph. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000109-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Square-root Decomposition adalah sebuah metode pendekomposisian sebuah permasalahan yang membuat sebuah operasi pada permasalahan dapat dilakukan dengan kompleksitas O(pN) [1]. Teknik Squareroot Decomposition sendiri dapat digunakan untuk menyelesaikan permasalahan-permasalahan yang berhubungan dengan query pada graf,tree,maupun array. Teknik ini juga merupakan dasar dari mo’s algorithm yang dapat digunakan untuk menyelesaikan permasalahan yang berhubungan dengan range-query [2] Tugas Akhir ini mengacu pada penerapan teknik Square-Root Decomposition dalam proses mendekomposisi graf untuk menyelesaikan permasalahan pada situs SPOJ dengan kode soal GRAPH2 bernama ”Graph”. Pada soal ini, akan diberikan sebuah graf berbobot tak berarah dengan masing-masing vertex memiliki warna putih atau hitam. Serta akan diberikan query-query yang dapat berbentuk operasi untuk merubah warna suatu vertex pada graf yang diberikan, ataupun meminta total berat edge yang menghubungkan vertex dengan warna tertentu. Untuk mengeksekusi query dengan efisien, graf akan didekomposisi menggunakan teknik Square-Root Decomposition sehingga setiap query dapat dieksekusi dalam kompleksitas tidak lebih dari O( pN). Berdasarkan uji coba yang dilakukan, implementasi Square-Root Decomposition dapat menyelesaikan permasalahan secara efisien dengan waktu rata-rata 0.485 detik serta penggunaan memori rata-rata 25.7 MB.
=================================================================================================================================
Square-root Decomposition is a decomposition method that allows an operation in a problem to be executed with O( p N) complexity [1]. The Square-root Decomposition technique can be used to solve problems that requires query on a raph,tree,or array. This technique is also became the base of mo’s algorithm that can be used to solve a problem related to range-queries. [2] This thesis refers to the implementation of the Square-Root Decomposition Technique [1] in the process of decomposing graph to solve the problem on SPOJ website with GRAPH2 as the problem code with the title ”Graph”. In this problem, will be given a weighted undirected graph with each vertex having one of two colors -black and white-. There will also be some queries with each query will be in the form of an operation to change a particular vertex’s color on the given graph or asking the total weight of edge that is connecting vertex of particular colors. To execute those queries efficiently, the given graph will be decomposed using Square-Root Decomposition Technique so that the queries can be executed in a complexity not worse than O( p N). Based on the test results,the implementation of Square-Root Decomposition technique can solve the problem efficiently with average time execution of 0.485 seconds and the average memory usage of 25.7 MB.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	akar kuadrat, dekomposisi graf, graf, Square-Root Decomposition, Graph, Graph Decomposition, Square-root, Square-Root Decompositon
Subjects:	T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	13 Oct 2025 03:51
Last Modified:	13 Oct 2025 03:51
URI:	http://repository.its.ac.id/id/eprint/128570

Actions (login required)

View Item