Research Report

Spectral Reconstruction and Isomorphism of graphs using variable neighbourhood search

Details

Citation

Caporossi G, Cvetkovic D & Rowlinson P (2013) Spectral Reconstruction and Isomorphism of graphs using variable neighbourhood search. Les Cahiers du GERAD, G-2013-73. GERAD. http://www.gerad.ca/fichiers/cahiers/G-2013-73.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 algorithm for 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

StatusPublished
Title of seriesLes Cahiers du GERAD
Number in seriesG-2013-73
Publication date31/10/2013
URLhttp://hdl.handle.net/1893/18447
PublisherGERAD
Publisher URLhttp://www.gerad.ca/fichiers/cahiers/G-2013-73.pdf
ISSN of series0711-2440

People (1)

People

Professor Peter Rowlinson

Professor Peter Rowlinson

Emeritus Professor, Mathematics