Topology for Optimal Task Assignment on Multicomputers with Dedicated Resources
Sang-Young Cho · International Journal of Software Engineering and Its Applications · 2014
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(n 3 k) time complexity of existing algorithms for the task assignment problems can be enhanced to O(n 3 logk) 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(n 3 k), where n is the number of nodes in a k-terminal graph, with the Goldberg-Tarjan’s network flow algorithm.