A Faster Isomorphism Test for Graphs of Small Degree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2018
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912333134036992 |
|---|---|
| author | Grohe, Martin Neuen, Daniel Schweitzer, Pascal |
| author_facet | Grohe, Martin Neuen, Daniel Schweitzer, Pascal |
| contents | In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time $n^{O((\log d)^{c})}$, where $n$ is the number of vertices of the input graphs, $d$ is the maximum degree of the input graphs, and $c$ is an absolute constant. The best previous isomorphism test for graphs of maximum degree $d$ due to Babai, Kantor and Luks (FOCS 1983) runs in time $n^{O(d/ \log d)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1802_04659 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | A Faster Isomorphism Test for Graphs of Small Degree Grohe, Martin Neuen, Daniel Schweitzer, Pascal Data Structures and Algorithms Discrete Mathematics Combinatorics Group Theory In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time $n^{O((\log d)^{c})}$, where $n$ is the number of vertices of the input graphs, $d$ is the maximum degree of the input graphs, and $c$ is an absolute constant. The best previous isomorphism test for graphs of maximum degree $d$ due to Babai, Kantor and Luks (FOCS 1983) runs in time $n^{O(d/ \log d)}$. |
| title | A Faster Isomorphism Test for Graphs of Small Degree |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics Group Theory |
| url | https://arxiv.org/abs/1802.04659 |