Optimized 2-Approximation of Treewidth
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912463868395520 |
|---|---|
| author | Belbasi, Mahdi Fürer, Martin Kumar, Medha |
| author_facet | Belbasi, Mahdi Fürer, Martin Kumar, Medha |
| contents | This paper presents a linear FPT algorithm to find a tree decomposition with a 2-approximation of the treewidth with a significantly smaller exponential dependence on the treewidth. The algorithm runs in time $O(\text{poly}(k) 81^k n)$, compared to Korhonen's running time of $O(\text{poly}(k) 1782^k n)$ = $O(2^{10.8k} n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16918 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimized 2-Approximation of Treewidth Belbasi, Mahdi Fürer, Martin Kumar, Medha Data Structures and Algorithms This paper presents a linear FPT algorithm to find a tree decomposition with a 2-approximation of the treewidth with a significantly smaller exponential dependence on the treewidth. The algorithm runs in time $O(\text{poly}(k) 81^k n)$, compared to Korhonen's running time of $O(\text{poly}(k) 1782^k n)$ = $O(2^{10.8k} n)$. |
| title | Optimized 2-Approximation of Treewidth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.16918 |