• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Colloquium on 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.
机译：我们研究了定向Parear图形的一些边缘的问题，使得所得到的子层强烈连接并跨越图表的所有顶点。我们对具有最小弧数的方向感兴趣，使得它们产生具有有界妊娠因子的数字。当传感器配备有方向天线时，这种取向具有建立强连接传感器网络的问题。我们为这种方向提出了三种结构。设g =（v，e）是没有切割边缘的连接平面图，让φ（g）是G.我们的结构基于面色着色，与λ颜色表示。第一次施工具有最多（2 - （4λ-6）/λ（λ-1））| e |最多φ（g） - 1.第二结构最多提供了强大的取向|弧和拉伸因子弧和拉伸因子至多（φ（g） - 1）〜（λ+ 1/2）。第三结构可以应用于3边缘连接的平面图。它使用特定的6面色着色，并且对于任何整数K> 1产生强大的取向，最多（1 - K / 10（k + 1））| e |弧形和拉伸因子至多φ〜2（g）（φ（g） - 1）〜（2k + 4）。这些是最糟糕的上限。实际上，拉伸因素取决于由路径遍历的面。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号