A robust algorithm for bisecting a triconnected graph with two resource sets
A robust algorithm for bisecting a triconnected graph with two resource sets
复制标题
DOI：
10.1016/j.tcs.2005.06.010
复制
发表时间：
2005-09
期刊：
影响因子：
--
通讯作者：
H. Nagamochi;K. Iwata;Toshimasa Ishii
中科院分区：
文献类型：
--
作者：
H. Nagamochi;K. Iwata;Toshimasa Ishii
给定3-连通图G=（V，E）中两个不相交的节点子集T1和T2，G =（V，E）具有一个节点集V和一个弧集E，其中|T1|和|T2|是偶数，已知V可以被划分为两个集合V1和V2，使得由V1和V2诱导的图都是连通的，|V1 Tj| =| V2 Tj| =| TJ|对于每个j= 1，2，/2成立。一个O（|V| 2log| V|）时间和O（|V| +| E|空间算法，其中G被嵌入到平面R2中，节点集被嵌入上的Ham-sandwich割二分.然而，该算法的简单实现需要高精度的真实的算法来区分R2上的一个大点集中的两个接近的点。在本文中，我们提出了一个O（|V| 2）时间和空间算法。新算法仍然是基于几何嵌入的，它不需要计算R2中的实际嵌入点，也不需要存储嵌入点的任何真实的个数，因此可以构造一个纯组合的解.虽然新算法似乎需要更多的空间复杂度，但它可以仅用|V|链表使得每个元素在[1，|V|].
Given two disjoint subsets T1and T2of nodes in a 3-connected graph G=(V,E) with a node set V and an arc set E, where |T1| and |T2| are even numbers, it is known that V can be partitioned into two sets V1and V2such that the graphs induced by V1and V2are both connected and |V1∩Tj|=|V2∩Tj|=|Tj|/2 holds for each j=1,2. An O(|V|2log|V|) time and O(|V|+|E|) space algorithm for finding such a bipartition has been proposed based on a geometric argument, where G is embedded in the plane R2and the node set is bipartitioned by a ham-sandwich cut on the embedding. A naive implementation of the algorithm, however, requires high precision real arithmetic to distinguish two close points in a large set of points on R2. In this paper, we propose an O(|V|2) time and space algorithm to the problem. The new algorithm, which remains to be based on the geometric embedding, can construct a solution purely combinatorially in the sense that it does not require computing actual embedded points in R2and thereby no longer needs to store any real number for embedded points. Although the new algorithm seems to need more space complexity, it can be implemented only with |V| linked lists such that each element stores an integer in [1,|V|].