...
首页> 外文期刊>Discrete Applied Mathematics >Tree spanners in planar graphs
【24h】

Tree spanners in planar graphs

机译:平面图中的树扳手

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       

摘要

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in polynomial time for t = 2, while it is NP-hard for any a ≥ 4; the case t = 3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum to for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for nay fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t = 3.
机译:图G的树t跨度是G的跨度子树T,其中每对顶点之间的距离最多是它们在G中的距离的t倍。Spanner问题已引起人们的关注,主要是在通信网络中。众所周知,对于一般的非加权图,可以在多项式时间内解决t = 2时确定树t跨度的问题,而对于任何a≥4来说,它都是NP难解的; t = 3的情况是开放的,但据推测很难。在本文中,我们考虑平面图中的树扳手。我们表明,即使对于平面未加权图,也很难确定树t跨度存在的最小值。另一方面,我们给出了一个针对不固定t的多项式算法,该算法针对具有有限面长的平面非加权图确定是否有树t跨度。此外,我们证明了可以在多项式时间内确定平面无权图在t = 3时是否具有树t跨度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号