Bewaard in:
| Hoofdauteur: | |
|---|---|
| Formaat: | Preprint |
| Gepubliceerd in: |
2020
|
| Onderwerpen: | |
| Online toegang: | https://arxiv.org/abs/2011.14730 |
| Tags: |
Voeg label toe
Geen labels, Wees de eerste die dit record labelt!
|
Inhoudsopgave:
- We give an isomorphism test that runs in time $n^{\operatorname{polylog}(h)}$ on all $n$-vertex graphs excluding some $h$-vertex vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time $n^{\operatorname{polylog}(n)}$ (Babai, STOC 2016) and $n^{f(h)}$ for some function $f$ (Grohe and Marx, SIAM J. Comp., 2015). Our result also unifies and extends previous isomorphism tests for graphs of maximum degree $d$ running in time $n^{\operatorname{polylog}(d)}$ (SIAM J. Comp., 2023) and for graphs of Hadwiger number $h$ running in time $n^{\operatorname{polylog}(h)}$ (SIAM J. Comp., 2023).