Repository: Freie Universit├Ąt Berlin, Math Department

A spectral assignment approach for the graph isomorphism problem

Klus, S. and Sahai, T. (2018) A spectral assignment approach for the graph isomorphism problem. Information and Inference: a Journal of the IMA .

Full text not available from this repository.

Official URL: https://academic.oup.com/imaiai/advance-article/do...

Abstract

In this paper, we propose algorithms for the graph isomorphism (GI) problem that are based on the eigendecompositions of the adjacency matrices. The eigenvalues of isomorphic graphs are identical. However, two graphs GA and GB can be isospectral but non-isomorphic. We first construct a GI testing algorithm for friendly graphs and then extend it to unambiguous graphs. We show that isomorphisms can be detected by solving a linear assignment problem (LAP). If the graphs possess repeated eigenvalues, which typically correspond to graph symmetries, finding isomorphisms is much harder. By repeatedly perturbing the adjacency matrices and by using properties of eigenpolytopes, it is possible to break symmetries of the graphs and iteratively assign vertices of GA to vertices of GB, provided that an admissible assignment exists. This heuristic approach can be used to construct a permutation which transforms GA into GB if the graphs are isomorphic. The methods will be illustrated with several guiding examples.

Item Type:Article
Subjects:Mathematical and Computer Sciences
Divisions:Department of Mathematics and Computer Science > Institute of Mathematics > BioComputing Group
ID Code:2246
Deposited By: BioComp Admin
Deposited On:23 Apr 2018 07:51
Last Modified:23 Apr 2018 07:51

Repository Staff Only: item control page