On K-terminal Cut Problem Of (n,n)-graph And 3-terminal Cut Problem Of (n,n+1)-graph

In the k-terminal cut problem, one is given an undirected edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. In the-recent years, the k-terminal cut problem is of considerable theoretical interest and arises in several applied area such as parallel and distributed computing, VLSI design, and networking, In this dissertation, we consider the k-terminal cut problem in (n,n) - graphs and 3-terminal cut problem in (n,n+1)-graphs which are both edge-weighted undirected simple connected planar graphs with distinct positive edge weights.Firstly, by investigating the structure of (n, n) - graphs, we prove an important theorem that the minimum k-terminal cut of (n,n)-graphs must include the minimum weighted edge on P_c (the only basic circuit in (n,n) -graphs), if it includes some edge on P_c .We can associate (n, n) - graphs with trees from this theorem. So combined with the O(kn) time algorithm to solve the k-terminal cut problem in trees, we propose an polynomial exact one to solve the same problem with the same time-complexity as in the tree, when there are not less than 2 terminals on P_c. Furthermore, we modify this algorithm to solve the problem for the case when there is less than 2 terminal on P_c, without increase the computing complexity. In fact, the modified one can be served as a generic algorithm to solve the k-terminal cut problem of (n,n) - graphs and runs faster than all the known ones to solve the problem when they applied to (n, n) - graphs (the lowest computing time-complexity is O(nk~3+(nlog n)k~2) for (n,n)-graphs). So the k-terminal cut problem of (n,n) -graphs can be solved more efficiently to some extent by the algorithms we propose.Secondly, based on the sorting of the (n,n + l) -graphs with 3 terminals them, we divide the 3-terminal cut problem of (n,n+1)-graphs into several subproblems.We present linear-time algorithms for them, associated with the linear one to solve the 3-terminal cut problem of planar graphs when all terminals are all on the same face.Combing such algorithms, we propose an linear-time one to solve the 3-terminal cut problem of (?,? + l)-graphs.This algorithm is a better choice compared with all the known ones to solve the 3-terminal cut problem( the lowest computing time- complexity is O(nMogn)) for (n,n + \)-graphs).