Pembandingan Kompleksitas Algoritma pada Penyelesaian Permasalahan Graph Isomorphism
| Main Authors: | Soetandyo, Ryan Nathan; Jurusan Teknik Informatika Institut Teknologi Sepuluh Nopember, Wijaya, Arya Yudhi; Jurusan Teknik Informatika Institut Teknologi Sepuluh Nopember, Soelaiman, Rully; Jurusan Teknik Informatika Institut Teknologi Sepuluh Nopember |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
Lembaga Penelitian dan Pengabdian Kepada Masyarakat (LPPM), ITS
, 2016
|
| Subjects: | |
| Online Access: |
http://ejurnal.its.ac.id/index.php/sains_seni/article/view/16682 http://ejurnal.its.ac.id/index.php/sains_seni/article/view/16682/2820 |
Daftar Isi:
- Graf adalah sebuah model yang direpresentasikan sebagai kumpulan titik atau simpul dan beberapa garis yang menghubungkan antar titik atau yang disebut sebagai edge. Graf bisa digunakan sebagai model berbagai macam relasi dalam berbagai macam bidang seperti fisika, biologi, dan teknologi informasi. Salah satu masalah yang muncul di graf adalah masalah isomorphism.Graf A dan graf B bisa dikatakan isomorphic jika semua simpul di graf A bisa dipetakan ke simpul di graf B secara bijeksi. Untuk bisa mengetahui apakah kedua graf bersifat isomorphic ada beberapa pilihan algoritma yang bisa digunakan seperti VF2, Schmidt & Druffel fast backtracking dan lain lain.Pada tugas akhir ini, akan diselesaian permasalahan dengan judul “ISOMORPH” pada situs penilaian daring SPOJ. Pada permasalahan tersebut akan terdapat beberapa graf yang harus dicari pasangan isomorphic nya. Permasalahan tersebut akan diselesaikan dengan menggunakan 2 macam algoritma yaitu algoritma VF2 dan algoritma Schmidt & Druffel fast Backtracking.