Efficient Algorithms for Tripartitioning Triconnected Graphs and 3-Edge-Connected Graphs
Efficient Algorithms for Tripartitioning Triconnected Graphs and 3-Edge-Connected Graphs
复制标题
用于三分三连通图和三边连通图的高效算法
DOI：
10.1007/3-540-57899-4_47
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Kimio Kawaguchi
中科院分区：
文献类型：
--
作者：
K. Wada;Kimio Kawaguchi
扩展k划分问题定义如下。对于下列输入：（1）一个无向图G=（V，E）（n = β V β，m= β E β），（2）一个顶点子集V′（α- V），（3）不同顶点aieV ′（1 ≤ i ≤ k）和（4）自然数ni（1 ≤ i≤k）（n1 ≤...≤ nk），使得n1 +. + nk =n′ = β V′ β，我们计算一个划分V1 β. V的V k和一个分割V′1. V′ k，使得（a）每个V′i包含在Vi中，（B）每个V′i包含指定的顶点ai，（c）β V′i β = ni，（d）每个Vi导出一个连通子图.如果V′ = V，则该问题称为k-划分问题。在本文中，我们证明了如果输入图是三连通的，则扩展的三分问题可以在O（m +（n-n3）· n）时间内解决，并且该算法在O（m +（n1 + n2）· n）时间内解决了原始的三分问题。此外，我们证明了对于k-边连通图G -（V，E），存在一个划分V1，V2，V3，V4，V5，V6，V8，V9，V10，V11，V12，V13，V14，V15，V16，V17，V18，V19 Vk，使得每个Vi包含指定的顶点ai，φ Vi β = ni和k个子图G1，.，Gk是边不相交的，每个Gi包含Vi（1 ≤ i ≤ k）中的所有元素，且k = 3的情况可在O（n2）时间内求解.
The extended k-partition problem is defined as follows. For the following inputs (1)an undirected graph G=(V, E)(n = ¦V¦, m= ¦E¦), (2)a vertex subset V′(⊂- V), (3)distinct vertices ai e V′(1 ≤ i ≤ k) and (4)natural numbers ni(1 ≤ i≤k)(n1 ≤ ... ≤ nk) such that n1 +... + nk =n′ = ¦V′¦, we compute a partition V1∪...∪V k of V and a partition V′1∪...V′ k of V′ such that (a)each V′i is included in Vi, (b)each V′i contains the specified vertex ai, (c)¦V′i¦ = ni and (d)each Vi induces a connected subgraph. If V′ = V, then the problem is called the k-partition problem. In this paper, we show that if the input graph is triconnected the extended tripartition problem can be solved in O(m + (n − n3) · n) time and that the algorithm solves the original tripartition problem in O(m + (n1 + n2) · n) time. Furthermore, we show that for a k-edgeconnected graph G - (V, E) there exists a partition V1 ∪ ... V k of V such that each Vi contains the specified vertex ai, ¦Vi¦ = ni and k subgraphs G1,..., Gk are mutually edge disjoint and each of Gi contains all of elements in Vi(1 ≤ i ≤ k) and the case in which k = 3 can be solved in O(n2) time.