A Faster Isomorphism Test for Graphs of Small Degree
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2018
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |