Scheduling real-time computations with separation constraints

Ching Chih Han*, Kwei Jay Lin

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

18 Scopus citations

Abstract

Given a graph and a positive integer k, the Separation Problem is to find a linear layout for the vertices such that each pair of adjacent vertices has a distance of at least k in the layout. A polynomial time algorithm has been studied earlier for the special case when the graph is a directed forest. In this paper, we study the problem when the roots of the trees in the forest have different constraints on their earliest starting positions. We present an O(n log n) algorithm for the problem with n vertices in the forest. We then use the algorithm to schedule real-time jobs with minimum distance constraints.

Original languageEnglish
Pages (from-to)61-66
Number of pages6
JournalInformation Processing Letters
Volume42
Issue number2
DOIs
StatePublished - 11 05 1992
Externally publishedYes

Keywords

  • Real-time systems
  • minimum distance constraint
  • separation problem

Fingerprint

Dive into the research topics of 'Scheduling real-time computations with separation constraints'. Together they form a unique fingerprint.

Cite this