Desain Dan Analisis Algoritma Penyelesaian Permasalahan Maximum Clique Pada Graf Studi Kasus: SPOJ ADAPARTY – Ada And Party

Arrafi, Muhammad (2021) Desain Dan Analisis Algoritma Penyelesaian Permasalahan Maximum Clique Pada Graf Studi Kasus: SPOJ ADAPARTY – Ada And Party. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111640000043-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Permasalahan SPOJ ADAPARTY – Ada and Party merupakan permasalahan pencarian kelompok pertemanan terbesar dalam sebuah jaringan pertemanan untuk diundang ke sebuah pesta, di mana setiap individu dalam kelompok tersebut saling mengenal satu dengan yang lainnya. Kelompok dari jaringan pertemanan tersebut merepresentasikan clique dari sebuah graf.
Permasalahan pencarian clique terbesar dari sebuah graf merupakan permasalahan maximum clique. Permasalahan maximum clique merupakan permasalahan NP-hard yang berarti tidak ada algoritma dalam waktu polinomial untuk menyelesaikan permasalahan ini. Penyelesaian secara naif akan menghasilkan kompleksitas waktu O(n!). Maka diperlukan algoritma heuristik untuk mendapatkan solusi yang efisien. Algoritma maximum clique merupakan algoritma heuristik.
Algoritma maximum clique menggunakan dua metode, yaitu metode branch and bound untuk melakukan pencacahan secara sistematis terhadap ruang solusi kemudian mengeksplorasinya dan metode pewarnaan graf dinamis untuk menghitung batas sampai mana eksplorasi dilakukan. Implementasi algoritma tersebut akan digunakan untuk menyelesaikan studi kasus SPOJ ADAPARTY.

========================================================

The problem of SPOJ ADAPARTY is the problem of finding the largest group of friends in a network of friends to be invited to a party, where each individual in the group knows each other. The group from the network of friends represents a clique of a graph.
The problem of finding the biggest clique of a graph is the maximum clique problem. The maximum clique problem is an NP-hard problem, which means that there is no algorithm in polynomial time to solve this problem. Solving naively will yield O (n!) Time complexity. So a heuristic algorithm is needed to get an efficient solution. The maximum clique algorithm is a heuristic algorithm.
The maximum clique algorithm uses two methods, namely the branch and bound method to systematically enumerate the solution space then explore it and the dynamic graph coloring method to calculate the boundary to which exploration is carried out. The algorithm implementation akandigunakan to resolve ADAPARTY SPOJ case studies.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	Algoritma Maximum Clique, Maximum Clique, NP-Hard, Pewarnaan Graf
Subjects:	T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis
Depositing User:	Muhammad Arrafi
Date Deposited:	11 Mar 2021 00:14
Last Modified:	11 Mar 2021 00:14
URI:	http://repository.its.ac.id/id/eprint/84100

Actions (login required)

View Item