Integer linear programming formulations for treewidth
AbstractIn this paper we consider an ILP-based approach to tackle the problem of determining a treewidth of the graph. We give an overview of existing attempts and develop further LP-based techniques for the problem. We present two different ILP formulations for the treewidth. To obtain the first one we merge the chordalization-based ILP by Koster and Bodlaender and flow metrics approach by Bornstein and Vempala. The second brand-new ILP is based on the structural properties of the tree-decomposition. It has a nice application of the local branching techniques by Fischetti and Lodi.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 030.
Date of creation: 2011
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
This paper has been announced in the following NEP Reports:
- NEP-ALL-2011-05-24 (All new papers)
You can help add them by filling out this form.
reading list or among the top items on IDEAS.Access and download statisticsgeneral information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.