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
Previous revision
Next revision Both sides next revision
2ima00 [2016/05/12 12:17]
bmpjansen [Student lectures]
2ima00 [2016/05/26 12:12]
bmpjansen [Student lectures]
Line 121: Line 121:
  
 === Programming pairs for implementation === === Programming pairs for implementation ===
 +The literature linked to below can be accessed when logged into the TU/e network, either through VPN or by physically being present at TU/e.
  
-Kernels: +**Kernels: Chris & Leo.**
-Chris & Leo.+
  
-Treewidth:​ +The following paper gives a kernel that is not as small, but is easier to compute, than the one given in the bookIn particular, read Section 4 of this paper:
-Henk & Xi.+
  
-Parameterized by solution size (iterative compression & randomized):​ +[[http://​dx.doi.org/​10.1007/​s00224-009-9234-2| 
-Huib & Stefan.+Hans L. Bodlaender, Thomas C. van Dijk: 
 +A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst. 46(3): 566-597 (2010)]] 
 + 
 +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: 
 + 
 +[[http://​dx.doi.org/​10.1137/​S0895480196305124|Vineet Bafna, Piotr Berman, Toshihiro Fujito: 
 +A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. SIAM J. Discrete Math. 12(3): 289-297 (1999)]] 
 + 
 +Option 2: 
 + 
 +[[https://​dx.doi.org/​10.1016%2F0004-3702%2895%2900004-6|Becker,​ Ann; Geiger, Dan (1996), "​Optimization of Pearl'​s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.",​ Artificial Intelligence 83 (1): 167–188]] 
 + 
 +**Treewidth:​ Henk & Xi.** 
 + 
 +[[https://​arxiv.org/​pdf/​1103.0534v1.pdf|Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time]] 
 +[[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) 
 + 
 +**Parameterized by solution size (iterative compression & randomized):​ Huib & Stefan.** 
 + 
 +[[http://​dx.doi.org/​10.1016/​j.ipl.2014.05.001|Tomasz Kociumaka, Marcin Pilipczuk:​ 
 +Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10): 556-560 (2014)]]
2ima00.txt · Last modified: 2016/05/26 12:27 by bmpjansen