• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Multipath Spanners
【24h】

Multipath Spanners

机译：多径扳手

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper concerns graph spanners that approximate mul-tipaths between pair of vertices of an undirected graphs with n vertices. Classically, a spanner H of stretch s for a graph G is a spanning subgraph such that the distance in H between any two vertices is at most s times the distance in G. We study in this paper spanners that approximate short cycles, and more generally p edge-disjoint paths with p > 1, between any pair of vertices.For every unweighted graph G, we construct a 2-multipath 3-spanner of O(n~(3/2)) edges. In other words, for any two vertices u,v of G, the length of the shortest cycle (with no edge replication) traversing u, v in the spanner is at most thrice the length of the shortest one in G. This construction is shown to be optimal in term of stretch and of size. In a second construction, we produce a 2-multipath (2, 8)-spanner of O(n~(3/2)) edges, i.e., the length of the shortest cycle traversing any two vertices have length at most twice the shortest length in G plus eight. For arbitrary p, we observe that, for each integer k ≥ 1, every weighted graph has a p-multipath p(2k -1)-spanner with O(pn~(1+1/k)) edges, leaving open the question whether, with similar size, the stretch of the spanner can be reduced to 2k - 1 for all p > 1.
机译：本文涉及图扳手，该扳手逼近具有n个顶点的无向图的一对顶点之间的多路径。传统上，图G的拉伸s的扳手H是一个跨越子图，因此任意两个顶点之间的H距离最多是G的距离的s倍。在本文中，我们研究的扳手近似于短周期，并且更一般地说在任意一对顶点之间有p> 1的p条边不相交路径，对于每个未加权图G，我们构造了一个O（n〜（3/2））边的2多径3跨距。换句话说，对于G的任意两个顶点u，v，扳手中穿过u，v的最短循环（无边缘复制）的长度最多是G中最短顶点的长度的三倍。在拉伸和尺寸方面达到最佳。在第二种构造中，我们产生O（n〜（3/2））边的2多径（2，8）跨度，即，遍历任何两个顶点的最短循环的长度最多为最短循环的两倍。 G的长度加8。对于任意p，我们观察到，对于每个k≥1的整数，每个加权图都有一个具有O（pn〜（1 + 1 / k））边的p多路径p（2k -1）-展宽对于所有p> 1，是否可以以相似的大小将扳手的拉长减小到2k-1。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号