Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs

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.