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

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