English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We here investigate on the complexity of computing the \emph{tree-length} andthe \emph{tree-breadth} of any graph $G$, that are respectively the bestpossible upper-bounds on the diameter and the radius of the bags in a treedecomposition of $G$. \emph{Path-length} and \emph{path-breadth} are similarlydefined and studied for path decompositions. So far, it was already known thattree-length is NP-hard to compute. We here prove it is also the case fortree-breadth, path-length and path-breadth. Furthermore, we provide a moredetailed analysis on the complexity of computing the tree-breadth. Inparticular, we show that graphs with tree-breadth one are in some sense thehardest instances for the problem of computing the tree-breadth. We give newproperties of graphs with tree-breadth one. Then we use these properties inorder to recognize in polynomial-time all graphs with tree-breadth one that areplanar or bipartite graphs. On the way, we relate tree-breadth with the notionof \emph{$k$-good} tree decompositions (for $k=1$), that have been introducedin former work for routing. As a byproduct of the above relation, we prove thatdeciding on the existence of a $k$-good tree decomposition is NP-complete (evenif $k=1$). All this answers open questions from the literature.

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