MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEComputing Treewidth by Integer Linear Programming
par Arie Koster
| Date : | 04/03/10 | | Time : | 10:00 | | Location : | Euler Violet |
The treewidth of a graph plays an important role in the area of fixed-parameter tractable algorithms. Computing treewidth is, however, NP-complete in general. After a brief discussion of heuristics, lower bounds, and preprocessing techniques, we study an exact method for computing treewidth: integer linear programming.
Page des séminaires
| 
