Desain dan Analisis Penerapan Maximum Clique pada Graf dengan Partisi Jamak Dalam Studi Kasus SPOJ 3009 – Revenge Of Voronoi

Wachid, Vania Rizky Juliana (2024) Desain dan Analisis Penerapan Maximum Clique pada Graf dengan Partisi Jamak Dalam Studi Kasus SPOJ 3009 – Revenge Of Voronoi. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201215-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2026. Download (7MB) | Request a copy

Abstract

Diagram Voronoi diskrit adalah bentuk turunan dari diagram Voronoi yang direpresentasikan dengan array dua dimensi huruf alfabet kecil. Setiap hurufnya menunjukkan daerah dari huruf tersebut dan setiap daerah mempunyai titik pusat. Pada persoalan ini digunakan jarak Manhattan untuk menghasilkan diagram Voronoi dua dimensi dari pusat – pusat daerah. Jika sebuah titik memiliki jarak yang sama terhadap beberapa pusat daerah, maka titik tersebut dimiliki oleh daerah dengan huruf paling kecil sesuai urutan abjad. Tugas Akhir ini berfokus pada permasalahan penentuan pusat daerah dari diagram yang diberikan. Permasalahan ini dikategorikan sebagai permasalahan classical pada Sphere Online Judge. Pada Tugas Akhir ini akan dibahas tentang analisis, desain, dan implementasi solusi dari permasalahan. Topik Tugas Akhir ini berkonsentrasi pada penerapan metode Maximum Clique dalam konteks graf berpartisi jamak, bertujuan untuk mengidentifikasi himpunan pusat daerah yang memungkinkan. Dalam penelitian ini, metode full searching diterapkan untuk menentukan batasan setiap daerah serta mengeksplorasi pasangan titik yang berpotensi menjadi pusat daerah. Selanjutnya, metode Depth First Search (DFS) digunakan untuk mengoptimalkan pengidentifikasian hubungan antar daerah. Hubungan daerah yang terbentuk selanjutnya diaplikasikan metode bruteforce untuk mencari himpunan titik pusat yang sesuai dari titik-titik yang berpotensi menjadi pusat daerah. Metode maximum clique ini sudah banyak penerapannya dalam bidang informatika hingga medis. Contohnya seperti pencarian kelompok individu kuat berdasarkan jejaring sosial hingga mengukur tingkat kesamaan antara dua struktur protein. Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan konsep maximum clique pada graf berpartisi jamak membutuhkan waktu rata rata 0,78 detik dan memori 5,2 MB.
=================================================================================================================================
The discrete Voronoi diagram is a derivative form of the Voronoi diagram, represented by a two-dimensional array of lowercase alphabet letters. Each letter indicates a region corresponding to that letter, with each region having a central point. In this problem, the Manhattan distance is used to generate a two-dimensional Voronoi diagram from the centers of these regions. If a point is equidistant to several region centers, it is assigned to the region corresponding to the smallest letter in alphabetical order. This Final Project focuses on the problem of determining the centers of regions from the given diagram. This problem is categorized as a classical problem on the Sphere Online Judge. The Final Project will discuss the analysis, design, and implementation of solutions to this problem. The topic of this Final Project concentrates on the application of the Maximum Clique method in the context of graphs with multiple partitions, aiming to identify possible sets of region centers. In this research, the Full Searching method is applied to determine the boundaries of each region and to explore pairs of points that could potentially be the centers of regions. Furthermore, the Depth First Search (DFS) method is used to optimize the identification of relationships between regions. The relationships between regions are then subjected to the bruteforce method to find the appropriate set of central points from the potential center points. The maximum clique method has found numerous applications in the fields of informatics to medicine. For instance, it is used in identifying strong individual groups based on social networks and measuring the similarity between two protein structures. Based on the test results on the given case study, the solution using the concept of maximum clique in graphs with multiple partitions have an average time of 0.78 seconds and 5.2 MB of memory.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Diagram Voronoi, Full searching, Maximum Clique, Full searching, Maximum Clique, Voronoi Diagram
Subjects:	T Technology > T Technology (General) > T57.74 Linear programming T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Vania Rizky Juliana Wachid
Date Deposited:	07 Feb 2024 07:51
Last Modified:	07 Feb 2024 07:51
URI:	http://repository.its.ac.id/id/eprint/106474

Actions (login required)

View Item