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

Koji GODA  Toshinori YAMADA  Shuichi UENO  

Publication
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
Keyword: 
scheduling,  NP-completeness,  approximation algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
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.