...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Bisecting a 4-connected graph with three resource sets
【24h】

Bisecting a 4-connected graph with three resource sets

机译：将四个连接的图与三个资源集平分

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

摘要

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T_1,T_2,…,Tk of nodes, called resource sets, where |Ti| is even for each i. The partition problem with k resource sets asks to find a partition V_1 and V_2 of the node set V such that the graphs induced by V_1 and V_2 are both connected and |V_1∩Ti|=|V_2∩Ti|=|Ti|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k_3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has k_4 as its subgraph, then a bisection exists and it can be found in O(|V|3log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.
机译：令G =（V，E）是具有节点集V和弧集E的无向图。G具有k个节点的成对的不相交子集T_1，T_2，…，Tk，称为资源集，其中| Ti |。甚至每个i。具有k个资源集的分区问题要求找到节点集V的分区V_1和V_2，使得由V_1和V_2诱导的图都被连接并且|V_1∩Ti| = |V_2∩Ti| = | Ti | / 2对于每个i = 1,2，...，k成立。已知即使在k ＝ 1的情况下，测试是否存在这样的二等分的问题也是NP难的。另一方面，已知如果对于k = 1,2，如果G与（k + 1）连接，那么对于任何给定的资源集都存在一个二等分，并且已经推测对于k_3，一个（k + 1 ）-连接图允许二等分。在本文中，我们表明对于k = 3，猜想不成立，而如果G是4连通的并且以k_4作为子图，则存在二等分，并且可以在O（| V | 3log | V中找到|）时间。此外，我们表明对于问题的弧形版本，对于k = 1,2,3，（k + 1）-边缘连接性就足够了。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号