@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",
}