Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2411.16918 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _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 |