(2020) Isomorphism Testing for Graphs Excluding Small Minors.
In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science.
Conference:
FOCS IEEE Symposium on Foundations of Computer Science
This is the latest version of this item.
|
Text
gi-excluded-minor-focs-cispa.pdf - Accepted Version Download (328kB) | Preview |
Official URL: https://ieeexplore.ieee.org/abstract/document/9317...
Abstract
We prove that there is a graph isomorphism test running in time n^{polylog(h)} on n-vertex graphs excluding some h-vertex graph as a minor. Previously known bounds were n^{poly(h)} (Ponomarenko, 1988) and n^{polylog(n)} (Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | FOCS IEEE Symposium on Foundations of Computer Science |
| Depositing User: | Daniel Neuen |
| Date Deposited: | 07 May 2021 15:44 |
| Last Modified: | 07 May 2021 15:44 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3398 |
Available Versions of this Item
- Isomorphism Testing for Graphs Excluding Small Minors. (deposited 07 May 2021 15:44) [Currently Displayed]
Actions
Actions (login required)
 |
View Item |