Han, Ching-Chih; Lin, Kwei-Jay Scheduling real-time computations with separation constraints. (English) Zbl 0768.68005 Inf. Process. Lett. 42, No. 2, 61-66 (1992). Summary: 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. Cited in 4 Documents MSC: 68M99 Computer system organization 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68R10 Graph theory (including graph drawing) in computer science 05C05 Trees Keywords:scheduling; real-time systems; separation problem; polynomial time algorithm; directed forest; trees; forest; minimum distance constraints PDF BibTeX XML Cite \textit{C.-C. Han} and \textit{K.-J. Lin}, Inf. Process. Lett. 42, No. 2, 61--66 (1992; Zbl 0768.68005) Full Text: DOI References: [1] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 [2] Han, C.-C.; Lin, K.-J., Scheduling jobs with temporal consistency constraints, Proc. 6th IEEE Workshop on Real-Time Operating Systems and Software, 18-23 (1989) [3] Han, C.-C.; Lin, K.-J., Job scheduling with temporal distance constraints, Tech. Rept. UIUCDCS-R-89-1560 (1989), Department of Computer Science, University of Illinois: Department of Computer Science, University of Illinois Urbana-Champaign [4] Leung, J. Y.-T.; Vornberger, O.; Witthoff, J. D., On some variants of the bandwidth minimization problem, SIAM J. Comput., 13, 650-667 (1984) · Zbl 0545.68058 [5] Papadimitriou, C. H., The NP-completeness of the bandwidth minimization problem, Computing, 16, 263-270 (1976) · Zbl 0321.65019 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.