Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees


Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we assume that every job is non-preemptive. Let C={1,2,...} be a color set. A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets. Such a multicoloring is called a non-preemptive scheduling. The cost non-preemptive scheduling problem is to find an optimal multicoloring of G.

Share and Cite:

Li, Y. , Ye, Z. and Zhou, X. (2012) Algorithm for Cost Non-preemptive Scheduling of Partial k-Trees. Open Journal of Applied Sciences, 2, 233-236. doi: 10.4236/ojapps.2012.24B053.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] H.L. Bodlaender, polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms 11, pp. 631-643, 1990.
[2] R.B. Borie, R.G. Parker and C.A. Tovey, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems of recursively constucted graph families, Algorithmica 7, pp.555-581, 1992.
[3] E. Balas and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM.J. Comput., 20, pp. 209-221, 1991.
[4] C.T. Hoang, Efficient algorithms for minimum weighted colouring of some classes of perfact graphs,Discreate Applied Mathemativs, 55, pp.133-143, 1994.
[5] T. Ito, T. Nishizeki and X. Zhou, Algorithms for multicolorings of partial k-trees, IEICE Trans. Inf&Syst., E86-D, pp 191-200, 2003.
[6] D. Karger, C. Stein and J. Wein, "Scheduling algorithms," in Algorithms and Theory of Computation, Handbook, ed. M.J. Atallah, CRC Press, 1998.
[7] E. Kubicka and A.J. Schwenk, An introduction to chromatic sum, Proc. 17th Annual ACM Computer Science Conf., pp. 39-45, 1989.
[8] A. Moukrim, K. Sghiouer, C. Lucet and Y. Li, Lower bounds for the minimal sum coloring problem, Electronic Noted in Discrete Mathematics, vol.36, pp.663-670, 2010.
[9] A. Oproscu and T. Kielmann, Bag-of-tasks scheduling under budget constraints, In Cloud Computing Technology and Science, 2010 IEEE Second International Conference, pp.351-359, 2010.
[10] A. Sen, H. Deng and S. Guha, On a graph partition problem with an application to VLSI layout, Information Processing Letters, 43, pp. 87-94, 1992.
[11] W. Shi and B. Hong, Resource allocation with a budget constraint for computing independent task in the cloud. In Cloud Computing Technology and Science, 2010 IEEE Second International Conference, pp. 327-334, 2010.
[12] S. Isobe, X. Zhou and T. Nishizeki, A polynomial-time algorithm for finding tital colorings of partial k-trees, International Journal of Foundations of Computer Science, 10, pp.171-194, 1999.
[13] X. Zhou and T Nishizeki, Multicolorings of series-parallel graphs, Algorithmica, 38, pp. 271-297, 2004.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.