Email this article New Invariants for the Graph Isomorphism Problem
- Authors: Gamkrelidze A.1, Varamashvili L.1, Hotz G.2
-
Affiliations:
- Iv. Javakhishvili Tbilisi State University
- Department of Computer Science, Saarland University
- Issue: Vol 218, No 6 (2016)
- Pages: 754-761
- Section: Article
- URL: https://ogarev-online.ru/1072-3374/article/view/238311
- DOI: https://doi.org/10.1007/s10958-016-3061-1
- ID: 238311
Cite item
Open Access
Access granted
Subscription Access
Abstract
In this paper, we introduce a novel polynomial-time algorithm to compute graph invariants based on the idea of a modified random walk on graphs. Though not proved to be a full graph invariant yet, our method gives the right answer for the graph instances other well-known methods could not compute (such as special Fürer gadgets and point-line incidence graphs of finite projective planes of higher degrees).
About the authors
A. Gamkrelidze
Iv. Javakhishvili Tbilisi State University
Author for correspondence.
Email: alexander.gamkrelidze@tsu.ge
Georgia, Tbilisi
L. Varamashvili
Iv. Javakhishvili Tbilisi State University
Email: alexander.gamkrelidze@tsu.ge
Georgia, Tbilisi
G. Hotz
Department of Computer Science, Saarland University
Email: alexander.gamkrelidze@tsu.ge
Germany, Saarbrücken
Supplementary files
