TY - CONF
T1 - Isomorphism of graphs with bounded eigenvalue multiplicity
T2 - Proceedings of the fourteenth annual ACM symposium on Theory of computing
Y1 - 1982
A1 - Babai,László
A1 - Grigoryev,D. Yu.
A1 - Mount, Dave
AB - 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.
JA - Proceedings of the fourteenth annual ACM symposium on Theory of computing
T3 - STOC '82
PB - ACM
CY - New York, NY, USA
SN - 0-89791-070-2
UR - http://doi.acm.org/10.1145/800070.802206
M3 - 10.1145/800070.802206
ER -