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

Show more

References

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