LEGAY , Sylvain

During the last decade, metric properties of the bags of tree-decompositions of graphs have been studied. Roughly, the length and the breadth of a tree-decomposition are the maximum diameter and radius of its bags respectively. The treelength and the treebreadth of a graph are the minimum length and breadth of its tree-decompositions...

We here investigate on the complexity of computing the tree-length and the tree-breadth of any graph G, that are respectively the best possible upper-bounds on the diameter and the radius of the bags in a tree decomposition of G. Path-length and path-breadth are similarly defined and studied for path decompositions. So far, it was already known...

During the last decade, metric properties of the bags of tree decompositions of graphs have been studied. Roughly, the length and the breadth of a tree decomposition are the maximum diameter and radius of its bags respectively. The treelength and the treebreadth of a graph are the minimum length and breadth of its tree decompositions...