Message Scheduling on Trees under a Generalized Line-Communication Model

Fremantle, Australia June 23-June 25

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778910

1999 International Symposium on Paral ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Dominique Barth Articles by Mario E. Valencia-Pabon

	ASCII Text	x
	Dominique Barth, Mario E. Valencia-Pabon, "Message Scheduling on Trees under a Generalized Line-Communication Model," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 10, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999.

	BibTex	x
	@article{ 10.1109/ISPAN.1999.778910, author = {Dominique Barth and Mario E. Valencia-Pabon}, title = {Message Scheduling on Trees under a Generalized Line-Communication Model}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1999}, issn = {1087-4089}, pages = {10}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778910}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Message Scheduling on Trees under a Generalized Line-Communication Model SN - 1087-4089 SP EP A1 - Dominique Barth, A1 - Mario E. Valencia-Pabon, PY - 1999 KW - Message Scheduling KW - Line-Communications KW - Bufferless Routing KW - Tree Networks KW - NP-completeness KW - Approximation Algorithms VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Dominique Barth, Universite Paris-Sud

Mario E. Valencia-Pabon, Universite Paris-Sud

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.

Index Terms:

Message Scheduling, Line-Communications, Bufferless Routing, Tree Networks, NP-completeness, Approximation Algorithms

Citation:

Dominique Barth, Mario E. Valencia-Pabon, "Message Scheduling on Trees under a Generalized Line-Communication Model," ispan, pp.10, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.