English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Isomorphism Testing for Graphs Excluding Small Minors

MPS-Authors
/persons/resource/persons252640

Neuen,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:2004.07671.pdf
(Preprint), 402KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Grohe, M., Neuen, D., & Wiebking, D. (2020). Isomorphism Testing for Graphs Excluding Small Minors. Retrieved from https://arxiv.org/abs/2004.07671.


Cite as: http://hdl.handle.net/21.11116/0000-0007-9943-1
Abstract
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.