
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Task Assignment in Homogeneous Linear Array Networks
BogLae JO CheolHoon LEE Dongmyun LEE Myunghwan KIM
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E74A
No.9
pp.26422648 Publication Date: 1991/09/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: LETTER Category: Algorithms, Data Structures and Computational Complexity Keyword:
Full Text: PDF(428.2KB)>>
Summary:
This letter deals with the problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NPcomplete in the general case, and thus intractable for systems with a large number of processors. Recently, an optimal algorithm with the time complexity of O(n^{2}m^{3} log n) has been suggested for the problem of assigning m interacting tasks to a linear array of n processors. They solved the problem by using the twoterminal network flow approach. In this letter, we propose a multiterminal network flow approach for the task assignment problem in homogeneous linear array networks. The task assignment problem for a homogeneous linear array network of n processors is first transformed into (n1) twoterminal network flow problems, and then solved in time no worse than O(nm^{3}) by applying the GoldbergTarjan's network flow algorithm for each twoterminal network flow problem.

