• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Strong Orientations of Planar Graphs with Bounded Stretch Factor
【24h】

Strong Orientations of Planar Graphs with Bounded Stretch Factor

机译：有界拉伸因子的平面图的强方向

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

摘要

We study the problem of orienting some edges of given planar graph such that the resulting subdigraph is strongly connected and spans all vertices of the graph. We are interested in orientations with minimum number of arcs and such that they produce a digraph with bounded stretch factor. Such orientations have applications into the problem of establishing strongly connected sensor network when sensors are equipped with directional antennae.We present three constructions for such orientations. Let G = (V, E) be a connected planar graph without cut edges and let Φ(G) be the degree of largest face in G. Our constructions are based on a face coloring, say with λ colors. First construction gives a strong orientation with at most (2 - 4λ-6/λ(λ-1)) E arcs and stretch factor at most Φ(G) - 1. The second construction gives a strong orientation with at most E arcs and stretch factor at most (Φ(G) -1)~([λ+1/2]). The third construction can be applied to planar graphs which are 3-edge connected. It uses a particular 6-face coloring and for any integer k ≥ 1 produces a strong orientation with at most (1 -k/10(k+1)) E arcs and stretch factor at most Φ~2(G)(Φ(G) - 1)~(2k+4). These are worst-case upper bounds. In fact the stretch factors depend on the faces being traversed by a path.
机译：我们研究了使给定平面图的某些边定向的问题，以使生成的子图牢固地连接并跨越图的所有顶点。我们对圆弧数量最少的方向感兴趣，这样它们就可以生成具有有限拉伸因子的有向图。当传感器配备定向天线时，这种定向方式可用于建立牢固连接的传感器网络的问题。针对这种定向方式，我们提出了三种构造。令G =（V，E）为不带切边的连通平面图，令Φ（G）为G中最大面的度数。我们的构造基于人脸着色，例如具有λ颜色。第一种构造具有最多（2-4个λ-6/λ（λ-1））E弧的强取向，而拉伸因子最多是Φ（G）-1。第二种构造具有最多E弧的强取向。拉伸因子最大为（Φ（G）-1）〜（[λ+ 1/2]）。第三构造可以应用于三边连接的平面图。它使用特定的6面着色，并且对于任何k≥1的整数，都将生成强方向，最多具有（1-k / 10（k + 1））个E弧，并且拉伸因子最多为Φ〜2（G）（Φ（ G）-1）〜（2k + 4）。这些是最坏情况的上限。实际上，拉伸因子取决于路径所经过的面。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号