×

Multicoloring trees. (English) Zbl 1054.68016

Summary: Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bach, M., The design of the UNIX operating system (1986), Prentice Hall: Prentice Hall Englewood cliffs, NJ
[2] Bell, M., Future directions in traffic signal control, Transportation Research Part A, 26, 303-313 (1992)
[3] Bar-Noy, A.; Bellare, M.; Halldórsson, M. M.; Shachnai, H.; Tamir, T., On chromatic sums and distributed resource allocation, Information and Computation, 140, 183-202 (1998), (doi:10.1006/inco.1997.2677) · Zbl 0895.68022
[4] Bar-Noy, A.; Halldórsson, M. M.; Kortsarz, G.; Shachnai, H.; Salman, R., Sum multicoloring of graphs, Journal of Algorithms, 37, 422-450 (2000), (doi:10.1006/jagm.2000.1106) · Zbl 0964.68105
[5] Bar-Noy, A.; Kortsarz, G., The minimum color-sum of bipartite graphs, Journal of Algorithms, 28, 339-365 (1998), (doi:10.1006/jagm.1998.0938) · Zbl 0936.68076
[6] Brucker, P.; Krämer, A., Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems, European Journal of Operational Research, 90, 214-226 (1996) · Zbl 0916.90144
[7] Chen, J.; Cidon, I.; Ofek, Y., A local fairness algorithm for gigabit LANs/MANs with spatial reuse, IEEE Journal on Selected Areas in Communications, 11, 1183-1192 (1993)
[8] Daikoku, K.; Ohdate, H., Optimal design for cellular mobile systems, IEEE Transactions on Vehicular Technology, VT-34, 3-12 (1985)
[9] Feige, U.; Kilian, J., Zero knowledge and the chromatic number, Journal of Computer and System Sciences, 57, 2, 187-199 (1998), (doi:10.1006/jcss.1998.1587) · Zbl 0921.68089
[10] Halldórsson, M. M.; Kortsarz, G., Tools for multicoloring with applications to planar graphs and partial \(k\)-trees, Journal of Algorithms, 42, 2, 334-366 (2002), (doi:10.1006/jagm.2001.1210) · Zbl 0993.05070
[11] Halldórsson, M. M.; Kortsarz, G.; Proskurowski, A.; Salman, R.; Shachnai, H.; Telle, J. A., Multi-coloring trees, (Proceedings of the Fifth International Computing and Combinatorics Conference (COCOON), Tokyo, Japan. Proceedings of the Fifth International Computing and Combinatorics Conference (COCOON), Tokyo, Japan, Lecture Notes in Computer Science, vol. 1627 (1999), Springer: Springer Berlin), 271-280
[12] Jansen, K., The optimum cost chromatic partition problem, (Proceedings of the Third Italian Conference on Algorithms and Complexity (CIAC). Proceedings of the Third Italian Conference on Algorithms and Complexity (CIAC), LNCS, 1203 (1997)), 25-36
[13] Kubale, M., Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors, European Journal of Operational Research, 94, 242-251 (1996) · Zbl 0949.68507
[14] E. Kubicka, The chromatic sum of a graph, Ph.D. Thesis, Western Michigan University, 1989; E. Kubicka, The chromatic sum of a graph, Ph.D. Thesis, Western Michigan University, 1989 · Zbl 1064.05062
[15] Lynch, N., Upper bounds for static resource allocation in a distributed system, Journal of Computer and System Sciences, 23, 254-278 (1981) · Zbl 0473.68022
[16] Marx, D., The complexity of tree multicolorings, (Proceedings of the 27th International Symposium on Mathematical Foundation of Computer Science (MFCS). Proceedings of the 27th International Symposium on Mathematical Foundation of Computer Science (MFCS), LNCS (2002)) · Zbl 1014.68117
[17] Szkaliczki, T., Routing with minimum wire length in the Dogleg-Free Manhattan model is NP-complete, SIAM Journal on Computing, 29, 1, 274-287 (1999) · Zbl 0937.68055
[18] Silberschatz, A.; Galvin, P., Operating System Concepts (1998), Addison-Wesley: Addison-Wesley New York · Zbl 0883.68037
[19] Styer, E.; Peterson, G., Improved algorithms for distributed resource allocation, (Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC) (1988)), 105-116
[20] Young, W. R., Advanced mobile phone service, introduction, background and objectives, Bell Systems Technical Report, 58, 1-14 (1973)
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.