Template-type: ReDif-Paper 1.0
Author-Name: Grigoriev Alexander 
Author-Name: Ensinck Hans 
Author-Name: Usotskaya Natalya 
Author-workplace-name: METEOR
Title: Integer linear programming formulations for treewidth
Abstract: In 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. 
Keywords: mathematical applications; 
Series: Research Memoranda
Creation-Date: 2011
Number: 030
File-URL: http://arnop.unimaas.nl/show.cgi?fid=22458
File-Format: application/pdf
File-Size: 1494963
Handle: RePEc:unm:umamet:2011030