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 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 },
     year = {2014},
     volume = {39},
     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
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
%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/