New invariants for the graph isomorphism problem

DOI10.1007/S10958-016-3061-1MaRDI QIDQ2373963zbMATH OpenOpenAlexFDO

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)

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

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)

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

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

Cites work

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

Cited in

(7)

• Applications of dimensionality reduction and exponential sums to graph automorphism
• scientific article; zbMATH DE number 3904629 (Why is no real title available?)
• Algorithmic aspects of algebraic methods for graph isomorphism testing
• An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants
• On the power of combinatorial and spectral invariants
• Algorithms for the graph isomorphism problem based on graph deregularisation
• ScrewBox: a randomized certifying graph-non-isomorphism algorithm

Describes a project that uses

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)