New invariants for the graph isomorphism problem

DOI10.1007/S10958-016-3061-1zbMATH Open1352.05129arXiv1212.3055OpenAlexW1909289562MaRDI QIDQ2373963FDOQ2373963

Authors: A. Gamkrelidze, L. Varamashvili, Günter Hotz 

Publication date: 14 December 2016

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Abstract: In this paper we introduce a novel polynomial-time algorithm to compute graph invariants based on the modified random walk idea on graphs. However not proved to be a full graph invariant by now, our method gives the right answer for the graph instances other well-known methods could not compute (such as special Furer Gadgets and point-line incidence graphs of finite projective planes of higher degrees

Full work available at URL: https://arxiv.org/abs/1212.3055

Recommendations

• Algorithmic aspects of algebraic methods for graph isomorphism testing
• Algorithms for the graph isomorphism problem based on graph deregularisation
• On the power of combinatorial and spectral invariants
• Graph algebras and the graph isomorphism problem
• Isomorphism testing algorithm for graphs: Incidence degree sequence method and applications

zbMATH Keywords

modified random walk on graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random walks on graphs (05C81)

Cites Work

• Random Graph Isomorphism
• An optimal lower bound on the number of variables for graph identification
• Does co-NP have short interactive proofs ?
• Title not available (Why is that?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Graph isomorphism is in the low hierarchy
• Title not available (Why is that?)
• PSL(2,q) as a collineation group of projective planes of small order
• A note on the graph isomorphism counting problem
• Title not available (Why is that?)
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs

Cited In (7)

• On the power of combinatorial and spectral invariants
• An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants
• Applications of dimensionality reduction and exponential sums to graph automorphism
• Algorithmic aspects of algebraic methods for graph isomorphism testing
• Algorithms for the graph isomorphism problem based on graph deregularisation
• ScrewBox: a randomized certifying graph-non-isomorphism algorithm
• Title not available (Why is that?)

Uses Software

• nauty

This page was built for publication: New invariants for the graph isomorphism problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373963)