...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
【24h】

Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs

机译：图和超图的Steiner根取向的近似最小-最大定理

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

摘要

Given an undirected hypergraph and a subset of vertices S subset of V with a specified root vertex r epsilon S, the STEINER ROOTFD-ORIENTATION problem is to find an orientation of all the hyperedges so that in the resulting directed hypergraph the "connectivity" from the root r to the vertices in S is maximized. This is motivated by a multicasting problem in undirected networks as well as a generalization of some classical problems in graph theory. The main results of this paper are the following approximate min-max relations: Given an undirected hypergraph H, if S is 2k-hyperedge-connected in H, then H has a Steiner rooted k-hyperarc-connected orientation. Given an undirected graph G, if S is 2k-element-connected in G, then G has a Steiner rooted k-element-connected orientation. Both results are tight in terms of the connectivity bounds. These also give polynomial time constant factor approximation algorithms for both problems. The proofs are based on submodular techniques, and a graph decomposition technique used in the STEINER TREE PACKING problem. Some complementary hardness results are presented at the end. (c) 2008 Elsevier Inc. All rights reserved.
机译：给定无向超图和V的子集S（具有指定的根顶点r epsilon S），STEINER ROOTFD-ORIENTATION问题将查找所有超边的方向，以便在所得的有向超图中，来自S中顶点的根r最大化。这是由于无向网络中的多播问题以及图论中一些经典问题的概括而引起的。本文的主要结果是以下近似的最小-最大关系：给定无向超图H，如果S是H中的2k-超边连接，则H具有Steiner根k-超圆连接的方向。给定一个无向图G，如果S在G中为2k元素连接，则G具有Steiner根k元素连接的方向。就连通性范围而言，这两个结果都很严格。这些还给出了两个问题的多项式时间常数因子近似算法。证明基于子模块技术，以及在STEINER TREE PACKING问题中使用的图分解技术。最后给出一些补充的硬度结果。 （c）2008 Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号