Geodesic
Spectral reconstruction and isomorphism of graphs using variable neighbourhood search
Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 39 (2014), p. 23 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

The Euclidean distance between the eigenvalue sequences of graphs $G$ and $H$, on the same number of vertices, is called the {\em 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 $\Gamma$ constructed from cospectral graphs $G$ and $H$, we can ensure that $G$ and $H$ are isomorphic if and only if the spectral distance between $\Gamma$ and $G+K_2$ 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.
Classification : 05C50 68P20 68R10
Keywords: spectral distance, graph angles, graph isomorphism, variable neighbourhood search. 
@article{BASS_2014_39_a1,
     author = {G. Caporossi and D. Cvetkovi\'c and P. Rowlinson},
     title = {Spectral reconstruction and isomorphism of graphs using variable neighbourhood search},
     journal = {Bulletin de l'Acad\'emie serbe des sciences. Classe des sciences math\'ematiques et naturelles},
     pages = {23 },
     publisher = {mathdoc},
     volume = {39},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASS_2014_39_a1/}
}
TY  - JOUR
AU  - G. Caporossi
AU  - D. Cvetković
AU  - P. Rowlinson
TI  - Spectral reconstruction and isomorphism of graphs using variable neighbourhood search
JO  - Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles
PY  - 2014
SP  - 23 
VL  - 39
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BASS_2014_39_a1/
LA  - en
ID  - BASS_2014_39_a1
ER  - 
%0 Journal Article
%A G. Caporossi
%A D. Cvetković
%A P. Rowlinson
%T Spectral reconstruction and isomorphism of graphs using variable neighbourhood search
%J Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles
%D 2014
%P 23 
%V 39
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BASS_2014_39_a1/
%G en
%F BASS_2014_39_a1
G. Caporossi; D. Cvetković; P. Rowlinson. Spectral reconstruction and isomorphism of graphs using variable neighbourhood search. Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 39 (2014), p. 23 . http://geodesic.mathdoc.fr/item/BASS_2014_39_a1/