Name
Abstract | ||
|---|---|---|
We give an algorithm, that given an n-vertex graph $G$ and an integer k, in time 2O(k)n either outputs a tree decomposition of $G$ of width at most 2k + 1 or determines that the treewidth of $G$ is larger than k. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms. In particular, our algorithm improves... |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/FOCS52979.2021.00026 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Upper bound,Heuristic algorithms,Approximation algorithms,Dynamic programming,Time complexity | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tuukka Korhonen | 1 | 0 | 3.38 |