PEMBANDINGAN KOMPLEKSITAS ALGORITMA PADA PENYELESAIAN PERMASALAHAN GRAPH ISOMORPHISM

Ryan Nathan Soetandyo, Arya Yudhi Wijaya, Rully Soelaiman
Submission Date: 2016-07-18 15:13:26
Accepted Date: 2016-11-23 18:14:55

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.


Keywords


Graf; Isomorphism; VF2; Schmidt & Druffel

References


DOUGLAS C. SCHMIDT, LARRY E. DRUFFEL. "A FAST BACTKTRACKING ALGORITHM TO TEST DIRECTED GRAPHS FOR ISOMORPHISM USING DISTANCE MATRICES." JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY 23, NO. 3 (JULY 1976): 433 - 445.

Jonatan L. Gross, Jay Yellen , Ping Zhang. Handbook Of Graph Theory Second Edition. Taylor & Francis Group, 2014.

L.P.Cordella, P.Foggia, C.Sansone, M.Vento. "Performance Evaluation of the VF Graph Matching Algorithm." IEEE, 1999: 1172-1177.

Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento. "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs." IEEE Transcations on Pattern Analysis and Machine Intelligence 26, no. 10 (Oktober 2004): 1367-1372.


Full Text: PDF

CC Licencing


Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).

Refbacks

  • There are currently no refbacks.


Lembaga Penjaminan Mutu, Pengelolaan dan Perlindungan Kekayaan Intelektual (LPMP2KI) ITS
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.