earticle

영어

One of the geometrical k-cut problem applications is the task assignment in homogeneous networks where processors are homogeneous and some of them have unique or special functionalities. Though the problem is NP-hard in general, there are polynomial-time optimal algorithms if the topology graphs representing networks have regular properties such as tree and general array. We showed that the O(n3k) time complexity of existing algorithms for the task assignment problems can be enhanced to O(n3logk) in cases of linear array, binary tree, and general array by using the results of [3, 5]. This paper also proposed a new kind of topology graphs on which the geometrical k-cut problem can be solved in polynomial time. The time complexity of the algorithm is O(n3k), where n is the number of nodes in a k-terminal graph, with the Goldberg-Tarjan’s network flow algorithm.