2ima00

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision | Next revision Both sides next revision | ||

2ima00 [2016/05/26 12:12] bmpjansen [Student lectures] |
2ima00 [2016/05/26 12:15] bmpjansen [Student lectures] |
||
---|---|---|---|

Line 143: | Line 143: | ||

**Treewidth: Henk & Xi.** | **Treewidth: Henk & Xi.** | ||

+ | |||

+ | There are 2 approaches for solving the problem when you have a tree decomposition. The first one has a running time of 3^k * poly(n), harder to understand, but may be easier to implement: | ||

[[https://arxiv.org/pdf/1103.0534v1.pdf|Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time]] | [[https://arxiv.org/pdf/1103.0534v1.pdf|Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time]] | ||

+ | |||

+ | The next approach has a worse factor f(k), but a better polynomial term (linear), and is conceptually simpler: | ||

+ | |||

[[http://link.springer.com/chapter/10.1007%2F3-540-36379-3_25|Ton Kloks, C.M. Lee, Jiping Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs]] (page 8 and further) | [[http://link.springer.com/chapter/10.1007%2F3-540-36379-3_25|Ton Kloks, C.M. Lee, Jiping Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs]] (page 8 and further) | ||

2ima00.txt ยท Last modified: 2016/05/26 12:27 by bmpjansen