Pembandingan Kompleksitas Algoritma Pada Penyelesaian Permasalahan Graph Isomorphism

Ryan Nathan Soetandyo • Arya Yudhi Wijaya • Rully Soelaiman
Journal article Jurnal Sains dan Seni ITS • 2016

Download full text
(Bahasa Indonesia, 4 pages)

Abstract

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.

Metrics

  • 218 views
  • 234 downloads

Journal

Jurnal Sains dan Seni ITS

Jurnal Sains dan Seni ITS merupakan publikasi ilmiah berkala yang diperuntukkan bagi mahasiswa I... see more