## 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.

Original language | English (US) |
---|---|

Title of host publication | Proc Euromicro Workshop Real Time |

Editors | Anon |

Publisher | Publ by IEEE |

Pages | 168-177 |

Number of pages | 10 |

ISBN (Print) | 0818619562 |

State | Published - Dec 1 1989 |

Externally published | Yes |

Event | Proceedings: Euromicro Workshop on Real Time - Villa Olma, Como, Italy Duration: Jun 14 1989 → Jun 16 1989 |

### Other

Other | Proceedings: Euromicro Workshop on Real Time |
---|---|

City | Villa Olma, Como, Italy |

Period | 6/14/89 → 6/16/89 |

## All Science Journal Classification (ASJC) codes

- Engineering(all)