@inproceedings{de51cce1d9b9415f80ad81d531849a5c,

title = "A parallel algorithm for mapping a special class of task graphs onto linear array multiprocessors",

abstract = "In parallel and distributed computing, mapping a task graph to a specific multiprocessor topology is an important problem. In this paper we investigate a special case of this problem for linear task graph and linear array multiprocessors. A polynomial time sequential algorithm and a parallel algorithm are developed and analyzed. It has been shown that the sequential algorithm developed has a time complexity at least as aood as the existing n log rz algorithm while the parallel algorithm presents the very first attempt at parallelizing the sequential solution. Further, we have proved that the partitioning problem is NP-complete for tree task graphs. Applications of the algorithm are briefly discussed.",

keywords = "Computational complexity, Load balancing, Multiprocessors, Parallel algorithms, Task graph partitioning",

author = "Sibabrata Ray and Hong Jiang and Deogun, {Jitender S.}",

note = "Publisher Copyright: {\textcopyright} 1994 ACM.; 1994 ACM Symposium on Applied Computing, SAC 1994 ; Conference date: 06-03-1994 Through 08-03-1994",

year = "1994",

month = apr,

day = "6",

doi = "10.1145/326619.326815",

language = "English (US)",

series = "Proceedings of the ACM Symposium on Applied Computing",

publisher = "Association for Computing Machinery",

pages = "473--477",

booktitle = "1994 ACM Symposium on Applied Computing, SAC 1994",

}