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 11:42] bmpjansen [Student lectures] |
2ima00 [2016/05/26 12:12] bmpjansen [Student lectures] |
||
---|---|---|---|

Line 124: | Line 124: | ||

**Kernels: Chris & Leo.** | **Kernels: Chris & Leo.** | ||

+ | |||

+ | The following paper gives a kernel that is not as small, but is easier to compute, than the one given in the book. In particular, read Section 4 of this paper: | ||

[[http://dx.doi.org/10.1007/s00224-009-9234-2| | [[http://dx.doi.org/10.1007/s00224-009-9234-2| | ||

Line 129: | Line 131: | ||

A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst. 46(3): 566-597 (2010)]] | A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst. 46(3): 566-597 (2010)]] | ||

- | This uses an approximation algorithm, which was developed independently by 2 sets of authors. Pick the one you find the easiest to read: | + | Instead of requiring an algorithm to find maximum matchings, it just needs an approximation algorithm for (weighted) feedback vertex set. It was developed independently by 2 sets of authors. Pick the one you find the easiest to read: |

Option 1: | Option 1: |

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