User Tools

Site Tools


2ima00

Differences

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

Link to this comparison view

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