ausblenden:
Schlagwörter:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM,Mathematics, Combinatorics, math.CO
Zusammenfassung:
We prove that there is a graph isomorphism test running in time
$n^{\operatorname{polylog}(h)}$ on $n$-vertex graphs excluding some $h$-vertex
graph as a minor. Previously known bounds were $n^{\operatorname{poly}(h)}$
(Ponomarenko, 1988) and $n^{\operatorname{polylog}(n)}$ (Babai, STOC 2016). For
the algorithm we combine recent advances in the group-theoretic graph
isomorphism machinery with new graph-theoretic arguments.
