Scheduling real-time computations with separation constraints. (English) Zbl 0768.68005

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.


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
Full Text: DOI


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