Skip header navigation
×

Article

Spectral Reconstruction and Isomorphism of graphs using variable neighbourhood search

Citation
Caporossi G, Cvetkovic D & Rowlinson P (2014) Spectral Reconstruction and Isomorphism of graphs using variable neighbourhood search. Bulletin, Classe des Sciences Mathematiques et Naturelles, Sciences Mathematiques, (39), pp. 23-38. http://elib.mi.sanu.ac.rs/files/journals/bltn/39/rad2.pdf

Abstract
The Euclidean distance between the eigenvalue sequences of graphs G and H, on the same number of vertices, is called the spectral distance between G and H. This notion is the basis of a heuristic algorithmfor reconstructing a graph with prescribed spectrum. By using a graph Γ constructed from cospectral graphs G and H, we can ensure that G and H are isomorphic if and only if the spectral distance between Γ and G + K2 is zero. This construction is exploited to design a heuristic algorithm for testing graph isomorphism. We present preliminary experimental results obtained by implementing these algorithms in conjunction with a meta-heuristic known as a variable neighbourhood search.

Keywords
spectral distance; graph angles; graph isomorphism; variable neighbourhood search

Journal
Bulletin, Classe des Sciences Mathematiques et Naturelles, Sciences Mathematiques, Issue 39

StatusPublished
Author(s)Caporossi, Gilles; Cvetkovic, Dragos; Rowlinson, Peter
Publication date31/12/2014
URLhttp://hdl.handle.net/1893/21311
PublisherInstitute of SANU, Belgrade
Publisher URLhttp://elib.mi.sanu.ac.rs/files/journals/bltn/39/rad2.pdf
ISSN0561-7332
Scroll back to the top