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
2ima00 [2016/05/26 12:25]
bmpjansen [Student lectures]
2ima00 [2016/05/26 12:27]
bmpjansen [Student lectures]
Line 153: Line 153:
  
 I don't know which of the 2 approaches will be faster on the inputs we have; one has a worse polynomial term, the other has a worse factor f(k). I don't think it is feasible to implement both, given the time. Pick one of the two and go for it. To **find** a tree decomposition,​ you can use one of the heuristics described in this paper: I don't know which of the 2 approaches will be faster on the inputs we have; one has a worse polynomial term, the other has a worse factor f(k). I don't think it is feasible to implement both, given the time. Pick one of the two and go for it. To **find** a tree decomposition,​ you can use one of the heuristics described in this paper:
- 
- 
  
 [[http://​dx.doi.org/​10.1016/​j.ic.2009.03.008|Hans L. Bodlaender, Arie M. C. A. Koster: [[http://​dx.doi.org/​10.1016/​j.ic.2009.03.008|Hans L. Bodlaender, Arie M. C. A. Koster:
 Treewidth computations I. Upper bounds. Inf. Comput. 208(3): 259-275 (2010)]] Treewidth computations I. Upper bounds. Inf. Comput. 208(3): 259-275 (2010)]]
 +
 +Within the framework of iterative compression and you have *some* feedback vertex set X in your graph G, you can also make a tree decomposition by making a tree decomposition for the forest G - X (which is easy) and then adding all vertices of X to all bags. Afterwards, you can try to make it better by removing vertices from X from bags when the tree decomposition remains valid after removing a vertex from a bag.
  
 **Parameterized by solution size (iterative compression & randomized):​ Huib & Stefan.** **Parameterized by solution size (iterative compression & randomized):​ Huib & Stefan.**
2ima00.txt ยท Last modified: 2016/05/26 12:27 by bmpjansen