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

The tree breadth ${\rm tb}(G)$ of a connected graph $G$ is the smallestnon-negative integer $\rho$ such that $G$ has a tree decomposition whose bagsall have radius at most $\rho$. We show that, given a connected graph $G$ oforder $n$ and size $m$, one can construct in time $O(m\log n)$ an additive tree$O\big({\rm tb}(G)\log n\big)$-spanner of $G$, that is, a spanning subtree $T$of $G$ in which $d_T(u,v)\leq d_G(u,v)+O\big({\rm tb}(G)\log n\big)$ for everytwo vertices $u$ and $v$ of $G$. This improves earlier results of Dragan andK\"{o}hler (Algorithmica 69 (2014) 884-905), who obtained a multiplicativeerror of the same order, and of Dragan and Abu-Ata (Theoretical ComputerScience 547 (2014) 1-17), who achieved the same additive error with acollection of $O(\log n)$ trees.

Additive Tree $O(\rho\log n)$-Spanners from Tree Breadth $\rho$