Periodic assignment and graph colouring. (English) Zbl 0807.05030
This paper deals with the problem of assigning periodic operations to a minimum number of identical processors under different constraints. The periodic assignment problem naturally arises in such diverse areas as real-time processing, vehicle scheduling and compiler design.
The authors consider two different models of scheduling: (1) unconstrained periodic assignment, where different executions of an operation may be assigned to different processors, and (2) constrained periodic assignment, where all executions of an operation have to be assigned to the same processor. They show that the latter case leads to an NP-hard problem of coloring circular-arc graphs and periodic-interval graphs. These two classes of graphs include interval graphs. The authors then prove that two heuristics for coloring circular-arc graphs require less than twice the minimum number of colors. Surprisingly, each general graph is a periodic-interval graph, so no such polynomial algorithm for periodic-interval graph is likely to exist.
The authors consider two different models of scheduling: (1) unconstrained periodic assignment, where different executions of an operation may be assigned to different processors, and (2) constrained periodic assignment, where all executions of an operation have to be assigned to the same processor. They show that the latter case leads to an NP-hard problem of coloring circular-arc graphs and periodic-interval graphs. These two classes of graphs include interval graphs. The authors then prove that two heuristics for coloring circular-arc graphs require less than twice the minimum number of colors. Surprisingly, each general graph is a periodic-interval graph, so no such polynomial algorithm for periodic-interval graph is likely to exist.
Reviewer: M.Kubale (Gdańsk)
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C90 | Applications of graph theory |
| 94C15 | Applications of graph theory to circuits and networks |
Keywords:
periodic assignment; NP-hard problem; coloring; circular-arc graphs; periodic-interval graphs; interval graphsReferences:
| [1] | Baruah, S. K.; Howell, R. R.; Rosier, L. E., On preemptive scheduling of periodic, real-time tasks on one processor, (Rovan, B., Mathematical Foundations of Computer Science 1990 (1990), Springer: Springer Berlin), 173-179 · Zbl 0734.68018 |
| [2] | Berger, B.; Rompel, J., A better performance guarantee for approximate graph colouring, Algorithmica, 5, 459-466 (1990) · Zbl 0697.68032 |
| [3] | Bondy, J. A.; Murthy, U. S.R., Graph Theory with Application (1976), Macmillan: Macmillan New York · Zbl 1226.05083 |
| [4] | Booth, S.; Lueker, S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [5] | Fredman, M. L.; Weide, B., On the complexity of computing the measure of \(U[a_i, b_{i\) · Zbl 0378.68032 |
| [6] | Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001 |
| [7] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [8] | Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H., The complexity of coloring circular arcs and chords, SIAM J. Algebraic Discrete Methods, 1, 216-227 (1980) · Zbl 0499.05058 |
| [9] | Gavril, F., Algorithms on circular-arc graphs, Networks, 4, 357-369 (1974) · Zbl 0309.05126 |
| [10] | Gilmore, P. C.; Hoffmann, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003 |
| [11] | Gupta, U. I.; Lee, D. T.; Leung, J. Y.-T., An optimal solution for the channel-assignment problem, IEEE Trans. Comput., 28, 807-810 (1979) · Zbl 0422.68031 |
| [12] | Hashimoto, A.; Stevens, J., Wire routing by optimizing channel assignment with large apertures, Proceedings of the 8th Design Automation Conference, 155-169 (1971) |
| [13] | Hopcroft, J. E.; Karp, R. M., An \(n^{52}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114 |
| [14] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041 |
| [15] | Korst, J. H.M.; Aarts, E. H.L.; Lenstra, J. K.; Wessels, J., Periodic multiprocessor scheduling, (Proceedings of the Conference on Parallel Architectures and Languages Europe, PARLE ’91, Vol. 505 (1991), Springer: Springer Berlin), 166-178, Lecture Notes in Computer Science |
| [16] | Korte, N.; Möhring, R. H., An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18, 68-81 (1989) · Zbl 0678.68043 |
| [17] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0358.68059 |
| [18] | Lekkerkerker, C. G.; Boland, J. Ch., Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501 |
| [19] | Leung, J. Y.-T.; Whitehead, J., On the complexity of fixed-priority scheduling of periodic, real-time tasks, Performance Evaluation, 2, 237-250 (1982) · Zbl 0496.90046 |
| [20] | Linial, L.; Vazirani, U., Graph products and chromatic numbers, Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 124-128 (1989) |
| [21] | Liu, C. L.; Layland, J. W., Scheduling algorithms for multiprogramming in a hard real-time environment, J. ACM, 20, 46-61 (1973) · Zbl 0265.68013 |
| [22] | Niven, I.; Zuckerman, H. S., An Introduction to the Theory of Numbers (1960), Wiley: Wiley New York · Zbl 0186.36601 |
| [23] | Orlin, J. B., Minimizing the number of vehicles to meet a fixed periodic schedule: an application of periodic posets, Oper. Res., 30, 760-776 (1982) · Zbl 0486.90054 |
| [24] | Orlin, J. B.; Bonuccelli, M.; Bovet, D., An \(O(n^2)\) algorithm for coloring proper circular arc graphs, SIAM J. Algebraic Discrete Methods, 2, 88-93 (1981) · Zbl 0496.68047 |
| [25] | Park, K. S.; Yun, D. K., Optimal scheduling of periodic activities, Oper. Res., 33, 690-695 (1985) · Zbl 0567.90053 |
| [26] | Shamos, M. I.; Hoey, D., Geometric intersections problems, Proceedings of the 17th Annual IEEE Symposium on Foundations of Computer Science, 208-215 (1976) |
| [27] | Shih, W.-K.; Hsu, W.-L., An \(O(n^{1.5})\) algorithm to color proper circular arcs, Discrete Appl. Math., 25, 321-323 (1989) · Zbl 0682.68062 |
| [28] | Teng, A.; Tucker, A., An O(qn) algorithm to \(q\)-color a proper family of circular arcs, Discrete Math., 55, 233-243 (1985) · Zbl 0567.68043 |
| [29] | Tucker, A., Coloring a family of circular arcs, SIAM J. Appl. Math., 29, 493-552 (1975) · Zbl 0312.05105 |
| [30] | Tucker, A., An efficient test for circular-arc graphs, SIAM J. Comput., 9, 1-24 (1990) · Zbl 0453.05054 |
| [31] | Welsh, D. J.A.; Powell, M. B., An upper bound on the chromatic number of a graph and its application to timetabling problems, Comput. J., 10, 85-87 (1967) · Zbl 0147.15206 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
