A Note on the Complexity of Scheduling for Precedence Constrained Messages in Distributed Systems

Koji GODA  Toshinori YAMADA  Shuichi UENO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.4   pp.1090-1092
Publication Date: 2005/04/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.4.1090
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
scheduling,  NP-completeness,  approximation algorithm,  

Full Text: PDF>>
Buy this Article

This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.