Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
type: Item
instance of: scholarly article
title: Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
zbMATH Open document ID: 0932.05064
author: S. A. Evdokimov
author: Ilya Ponomarenko
published in: Combinatorica
publication date: 2000-02-21T00:00:00Z
review text: The complexity of the graph isomorphism problem is unknown: for general graphs with \(n\) vertices the best known upper bound is \(n^{O(\sqrt{n/\log n})}\). If the multiplicities of the eigenvalues of the graph are bounded by \(k\), an algorithm of complexity \(n^{O(k)}\) is known. This is now reduced to \(c_k n^{O(1)}\).
reviewed by: András Recski
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 1404390
zbMATH Keywords: coloured graphs
zbMATH Keywords: Jordan blocks
MaRDI profile type: Publication
full work available at URL: s004930050059
OpenAlex ID: W2035859428
DOI: 10.1007/S004930050059
description: scientific article; zbMATH DE number 1404390