A Simple Algorithm for a Computationally Hard Problem

2018/08/06 by Farhadian, Ameneh
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1808.02070

Abstract

Graph isomorphism problem is a known hard problem. In this paper, a novel randomized algorithm is proposed for this problem which is very simple and fast. It solves the graph isomorphism problem with running time O(n².373) for any pair of n-vertex graphs whose adjacency matrices are not strongly co-det. Strongly co-det pair of matrices have very special symmetric structure which can be disarranged to be not strongly co-det by manipulating one element of the matrices.

Related

• Heuristic algorithm for solving of the graph isomorphism problem
• The direct algorithm for solving of the graph isomorphism problem
• Continuous optimization methods for the graph isomorphism problem
• A Polynomial Time Algorithm for Graph Isomorphism
• Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods