%0 Conference Paper
%B Proceedings of the fourteenth annual ACM symposium on Theory of computing
%D 1982
%T Isomorphism of graphs with bounded eigenvalue multiplicity
%A Babai,László
%A Grigoryev,D. Yu.
%A Mount, Dave
%X We investigate the connection between the spectrum of a graph, i.e. the eigenvalues of the adjacency matrix, and the complexity of testing isomorphism. In particular we describe two polynomial time algorithms which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity. If X and Y are graphs of eigenvalue multiplicity m, then the isomorphism of X and Y can be tested by an O(n4m+c) deterministic and by an O(n2m+c) Las Vegas algorithm, where n is the number of vertices of X and Y.
%B Proceedings of the fourteenth annual ACM symposium on Theory of computing
%S STOC '82
%I ACM
%C New York, NY, USA
%P 310 - 324
%8 1982///
%@ 0-89791-070-2
%G eng
%U http://doi.acm.org/10.1145/800070.802206
%R 10.1145/800070.802206