On computing tree and path decompositions with metric constraints on the bags

Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse

We here investigate on the complexity of computing the \emph{tree-length} and the \emph{tree-breadth} of any graph $G$, that are respectively the best possible upper-bounds on the…