@inproceedings{588ce1df3c654c9990971c5148aa10a7,
title = "Routing messages with release time and deadline constraints",
abstract = "The problem of deciding if a set of real-time messages can be transmitted in an unidirectional ring network with m > 1 nodes is considered. Complexity results are given for various restrictions on the four parameters associated with each message: origin node, destination node, release time and deadline. For nonpreemptive transmission, it is shown that the problem is solvable in polynomial time for any case when only one of the four parameters is allowed to be arbitrary. Also shown is that it is NP-complete for each case when any two of the four parameters are fixed. For preemptive transmission, the problem is solvable in polynomial time for any case when only one of the four parameters is allowed to be arbitrary. Also, it is NP-complete for each case when any two of the four parameters are fixed, except the following two cases: (1) same origin node and release time; and (2) same destination node and deadline.",
author = "Leung, {Joseph Y.T.} and Tam, {Tommy W.} and Wong, {C. S.} and Young, {Gilbert H.}",
year = "1989",
language = "English (US)",
isbn = "0818619562",
series = "Proc Euromicro Workshop Real Time",
publisher = "Publ by IEEE",
pages = "168--177",
editor = "Anon",
booktitle = "Proc Euromicro Workshop Real Time",
note = "Proceedings: Euromicro Workshop on Real Time ; Conference date: 14-06-1989 Through 16-06-1989",
}