论文标题
添加树$ O（ρ\ log n）$ - 树宽$ρ$的跨度
Additive Tree $O(ρ\log n)$-Spanners from Tree Breadth $ρ$
论文作者
论文摘要
连接的图形$ g $的树宽$ {\ rm tb}（g）$是最小的非负整数$ρ$，因此$ g $具有一个树的分解，其袋子的袋子最多都有$ρ$。我们表明，给定一个连接的图形$ g $的订单$ n $和尺寸$ m $，一个人可以在时间$ o（m \ log n）$中构建加性树$ o \ big（{\ rm tb}（g）\ log n \ n \ big）$ g $的$ g $，即$ g $ g $ g $ g $ g $ d_ p d _ D_G（U，V）+O \ big（{\ rm tb}（g）\ log n \ big）$每两个顶点$ u $和$ g $的$ v $。这改善了Dragan和Köhler的早期结果（Algorithmica 69（2014）884-905），他们获得了相同订单的乘法误差，以及Dragan和Abu-ATA（理论计算机科学547（2014）1-17），他在$ O（\ log log n n）$ of of of of of $ o（\ log n n）$ of（\ log n）$ pree flaper and dricalistry误差。
The tree breadth ${\rm tb}(G)$ of a connected graph $G$ is the smallest non-negative integer $ρ$ such that $G$ has a tree decomposition whose bags all have radius at most $ρ$. We show that, given a connected graph $G$ of order $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 every two vertices $u$ and $v$ of $G$. This improves earlier results of Dragan and Köhler (Algorithmica 69 (2014) 884-905), who obtained a multiplicative error of the same order, and of Dragan and Abu-Ata (Theoretical Computer Science 547 (2014) 1-17), who achieved the same additive error with a collection of $O(\log n)$ trees.
