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 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 matchingsit 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