Tree decompositions and routing problems

Bi Li 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts. In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k 4, we prove it is NP-Hard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014. In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomial-Time algorithm that either returns an induced cycle of length at least k+1 of a graph G or compute a k-Good tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica. In the second part of the thesis, we focus on routing problems.
Document type :
Liste complète des métadonnées

Cited literature [179 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Saturday, March 7, 2015 - 12:06:31 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Monday, June 8, 2015 - 10:16:23 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01127108, version 1



Bi Li. Tree decompositions and routing problems. Other [cs.OH]. Université Nice Sophia Antipolis, 2014. English. ⟨NNT : 2014NICE4088⟩. ⟨tel-01127108⟩



Record views


Files downloads