Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-111 | 15th August 2014 11:37

Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

RSS-Feed




TR14-111
Authors: Vikraman Arvind, Gaurav Rattan
Publication: 22nd August 2014 10:24
Downloads: 3036
Keywords: 


Abstract:

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous
best running time bound of $O^*(2^{O(k^2/\log
k)})$.



ISSN 1433-8092 | Imprint