7ème Cours Cours MPRI 2010–2011

7eme Cours Cours MPRI 2010{20117eme CoursCours MPRI 2010{2011Michel Habibhabib@liafa.jussieu.frhttp://www.liafa.jussieu.fr/ habib~Chevaleret, november 20107eme Cours Cours MPRI 2010{2011ScheduleSome remarks on treewidthBranch decomposition and connectivity functionsCoping with branchwidthRelationships between treewidth and branchwidthRankwidthSome relationships between these widthsThe boolean matrix multiplication complexity barrier7eme Cours Cours MPRI 2010{2011Some remarks on treewidthSome applications of treewidthI Packman from V. Limouzy (f^ete de la science 2007)Playing with Packman is equivalent to compute the treewidthof a special graph (3 or 4)I Treewidth de l’internet ...... Laurent ViennotFor a network of routers N, 80 treewidth(N) 1607eme Cours Cours MPRI 2010{2011Some remarks on treewidthExamples of non constructive algorithms1. For any xed k, it is polynomial to test wheter genius(G ) k(we know there is a nite number of obstructions)2. It is polynomial to decide if a graph has a non-crossingembedding in 3D(non-crossing means no 2 cycles cross)7eme Cours Cours MPRI 2010{2011Some remarks on treewidthB. Reed’s algorithm for disjoint path problem1. If treewidth(G ) k then using Courcelle’s meta theorem, itcan be solved in linear time.2. Else G contains a grid G as minor and we nd a vertex xr;rs.t. :G has a solution i G x has a solution.3. Recurse on G x7eme Cours Cours MPRI 2010{2011Some remarks on ...