Title :
Message scheduling on trees under a generalized line-communication model
Author :
Barth, Dominique ; Valencia-Pabon, Mario E.
Author_Institution :
LRI-URA CNRS, Univ. de Paris-Sud, Orsay, France
Abstract :
In this paper, we generalize the line-communication model by relaxing the notion of conflictness between paths. We show that the problem of finding optimal schedules to route any set of messages under both our generalized line-communication model and the bufferless routing model is NP-hard even if restricted to binary trees. Finally, a simple offline 2-approximation algorithm for our model on trees is presented
Keywords :
approximation theory; communication complexity; message passing; message switching; multiprocessor interconnection networks; network routing; scheduling; switching theory; trees (mathematics); NP-hard problem; binary trees; bufferless routing model; generalized line-communication model; message routing; message scheduling; offline 2-approximation algorithm; optimal schedules; path conflictness; tree networks; Binary trees; Electronic switching systems; Emulation; Processor scheduling; Routing;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1999. (I-SPAN '99) Proceedings. Fourth InternationalSymposium on
Conference_Location :
Perth/Fremantle, WA
Print_ISBN :
0-7695-0231-8
DOI :
10.1109/ISPAN.1999.778910
