论文标题
具有很少的P4和（K，L） - 图的图形T-Spanner的更简单有效的表征
Simpler and efficient characterizations of tree t-spanners for graphs with few P4's and (k, l)-graphs
论文作者
论文摘要
图$ g $的树$ t $ - 是一个生成的树$ t $，其中任何两个相邻的顶点$ g $之间的距离最多都是$ t $。 $ g $具有树$ t $ spanner的最小$ t $称为树伸展指数。 $ t $可加权的问题旨在决定树伸展指数最多是$ t $。关于其优化版本，$ g $的最小$ t $是$ t $添加的$ g $的拉伸指数，由$σ_t（g）$表示。给定带有$ n $顶点和$ m $边缘的图表，可以完成$ 2 $可加速图的识别$ O（n+m）$时间，而$ t $ - 加热性对于$σ_t（g）\ leq t $，$ t $，$ t \ egeq 4 $ and decitive $ t $ t = 3 $ np = 3 $ np = 3 $ 20。由于类的结构知识可以决定分类$ 3 $ - 加热的复杂性，因此在本文中，我们提出了更简单，更快的算法，以检查$ 2 $和$ 3 $ - 适用于$ p_4 $ s and $（k，\ ell）$的图形家庭。关于$（0，\ ell）$ - 图，我们为这些图的拉伸索引提供了下限和上限，并表征其拉伸索引等于所提出的上限的图形。此外，我们证明，即使对于细分图的线图，$ t $ - 可加权也是NP完整的。
A tree $t$-spanner of a graph $G$ is a spanning tree $T$ in which the distance between any two adjacent vertices of $G$ is at most $t$. The smallest $t$ for which $G$ has a tree $t$-spanner is called tree stretch index. The $t$-admissibility problem aims to decide whether the tree stretch index is at most $t$. Regarding its optimization version, the smallest $t$ for which $G$ is $t$-admissible is the stretch index of $G$, denoted by $σ_T(G)$. Given a graph with $n$ vertices and $m$ edges, the recognition of $2$-admissible graphs can be done $O(n+m)$ time, whereas $t$-admissibility is NP-complete for $σ_T(G) \leq t$, $t \geq 4$ and deciding if $t = 3$ is an open problem, for more than 20 years. Since the structural knowledge of classes can be determinant to classify $3$-admissibility's complexity, in this paper we present simpler and faster algorithms to check $2$ and $3$-admissibility for families of graphs with few $P_4$'s and $(k,\ell)$-graphs. Regarding $(0,\ell)$-graphs, we present lower and upper bounds for the stretch index of these graphs and characterize graphs whose stretch indexes are equal to the proposed upper bound. Moreover, we prove that $t$-admissibility is NP-complete even for line graphs of subdivided graphs.
