ALGORITMA BRANCH AND BOUND UNTUK MENDETEKSI CLIQUE PADA KECAMATAN SYIAH KUALA KOTA BANDA ACEH

Abstract

Kota Banda Aceh merupakan ibu kota provinsi Aceh yang memiliki akses jalan yang sangat banyak, baik itu jalan utama maupun jalan-jalan kecil yang menghubungkan antar desa (Gampong). sehingga perlu mengetahui daerah-daerah mana saja yang memiliki akses jalan yang banyak agar tidak terjadi perulangan melintasi jalan yang sama apabila ingin berpindah dari suatu daerah kedaerah lainnya. Oleh sebab itu perlu mengelompokkan daerah-daerah mana saja yang langsung terhubung dan membentuk cycle (clique) dan mencari kelompok yang bernilai maksimum berdasarkan nilai jarak yang dimiliki masing-masing kelompok, yang disebuk sebagai clique maksimum. Selanjutnya dilakukan pencarian clique maksimum dimana masing-masing kelompok clique akan dicatat jumlah verteks yang saling terhubung satu sama lain dan akan diperoleh clique dengan jumlah verteks paling banyak (Maksimum). Proses ini disebut sebagai proses bounding. Pada kecamatan Syiah Kuala Kota Banda Aceh diperoleh clique sebanyak 3 buah yaitu 2 buah clique berukuran 4 {E, G, F, H}, {E, G, F, D}, dan 1 buah clique berukuran 3 {E, G, I}. Clique maksimum yang diperoleh ialah clique dengan ukur 4 dimana jumlah verteks yang saling terhubung ialah 4 buah verteks. Pada penelitian ini juga diperoleh clique maksimal EGFD yaitu clique maksimum yang memiliki nilai bobot paling besar