Evaluation of Metaheuristics for Robust Graph Coloring Problem

• Autorzy: Zbigniew Kokosiński , Łukasz Ochał
• Języki publikacji: EN

Abstrakty

EN

In this paper a new formulation of the robust graph coloring problem (RGCP) is proposed. In opposition to classical GCP defined for the given graph G(V,E) not only elements of E but also Ē can be subject of color conflicts in edge vertices. Conflicts in Ē are assigned penalties 0

Słowa kluczowe

EN

Graphs; Algorithms

PL

Grafy; Algorytmy

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 519--524

Twórcy

autor

Zbigniew Kokosiński

• Cracow University of Technology, Poland

autor

Łukasz Ochał

• Cracow University of Technology, Poland

Bibliografia

• E. Alba (Ed.), Parallel metaheuristic - a new class of algorithms, John Wiley & Sons, 2005. DOI: 10.1002/0471739383
• C. Archetti, N. Bianchessi and A. Hertz, "A branch-and-price algorithm for the robust graph coloring problem", Les Cahiers du Gerad, G-2011-75, Montreal, 2011.
• H. Bouziri, M. Jouini, "A tabu search approach for the sum coloring problem", Electronic Notes in Discrete Mathematics, Vol. 36, pp. 915-922, 2010 DOI:10.1016/j.endm.2010.05.116
• R. L. Bracho, J. R. Rodriguez, F. J. Martinez : "Algorithms for Robust Graph Coloring on Paths", in Proc. 2nd International Conference on Electrical and Electronics Engineering, Mexico, pp. 9-12, IEEE 2005. DOI: 10.1109/ICEEE.2005.1529561
• G. Chrząszcz, Parallel evolutionary algorithm for robust scheduling in power systems, M.Sc. thesis, Cracow University of Technology, (in Polish) 2009.
• J. Dąbrowski, "Parallelization techniques for tabu search", in Proc. 8th Int. Conference on Applied Parallel Computing: State of the Art in Scientific Computing. - 2007.
• S. Deleplanque, J.-P. Derutin, A. Quilliot, "Anticipation in the Dial-aRide Problem: an introduction to the robustness", Proc. of the 2013 Federated Conference on Computer Science and Information Systems, FedCSIS'2015, Kraków, Poland, pp. 299-305, 2013.
• A. Dey, R. Pradhan, A. Pal, T Pal, "The Fuzzy Robust Graph Coloring Problem", in S. C., Biswal B. N., Udgata S. K., Mandal J.K. (Eds.) in Proc. of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2014, Vol. 1, Advances in Inteligent Systems and Computing Proceedings, Vol. 327, pp. 805- 813, Springer 2015. DOI: 10.1007/978-3-319-11933-5_91
• R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, Freeman, 1979.
• M. Gendreau, J. Y. Potvin (Eds.), Handbook of metaheuristics, International Series in Operations Research & Management Science, Springer US, 2010. DOI: 10.1007/978-1-4419-1665-5
• F. Glover, G. A. Kochenberger (Eds.), Handbook of metaheuristics, Kluwer 2003.
• B. Gładysz, "Fuzzy robust courses scheduling problem", Fuzzy Optimization and Decision Making, Vol. 6, pp. 155-161, 2007. DOI: 10.1007/s10700-007-9303-0
• G. Hutchinson, "Partitioning algorithms for finite sets", Comm. ACM, No. 6, pp. 613-614, 1963.
• T. R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience, 1995.
• D. S. Johnson, M. A. Trick: Cliques, coloring and satisfiability: Second DIMACS Implementation Challenge, DIMACS Series in Discr. Math. and Theor. Comp. Sc. Vol. 26, 1996.
• Z. Kokosiński, M. Kołodziej, K. Kwarciany, "Parallel genetic algorithm for graph coloring problem", in Proc. of the International Conference on Computational Science, ICCS'2004, LNCS, Vol. 3036, pp. 215-222, 2008. DOI: 10.1007/978-3-540-24685-5_27
• Z. Kokosiński, "Parallel metaheuristics in graph coloring", Bulletin of the National University "Lviv Politechnic", Series: Computer sciences and information technologies, No. 744 , pp. 209-214, 2012.
• M. Kubale (Ed.): Graph colorings, American Mathematical Society, 2004. DOI: 10.1090/conm/352
• A. Lim, F. Wang, "Metaheuristic for robust graph coloring problem", in Proc. 16th IEEE Int. Conference on Tools with Artificial Intelligence, ICTAI. - 2004.
• A. Lim, F. Wang, "Robust graph coloring for uncertain supply chain management", in Proc. 38th Annual Hawaii Int. Conf. on System Science, HICSS 2005, p. 81b, IEEE 2005. DOI : 10.1109/HICSS.2005.526
• S. Łukasik, Z. Kokosiński, G. Świętoń, "Parallel simulated annealing algorithm for graph coloring problem", in Proceedings of the Int. Conference Parallel Processing and Applied Mathematics, PPAM'2007, LNCS, Vol. 4967, pp. 229-238, 2008. DOI: 10.1007/978-3-540-68111-3_25
• A. Pahlavani, K. Eshghi, "A hybrid algorithm of simulated annealing and tabu search for graph colouring problem", International Journal of Operational Research, Vol.11, No.2, pp. 136-159, 2011. DOI: 10.1504/IJOR.2011.040694
• D. Ruta, "Robust Method of Sparse Feature Selection for Multi-Label Classification with Naive Bayes", Proc. of the 2014 Federated Conference on Computer Science and Information Systems, FedCSIS'2014, Warsaw, Poland, pp. 375-380, 2014. DOI: 10.15439/2014F502
• F. Wang, Z. Xu, "Metaheuristics for robust graph coloring", Journal of Heuristics, Vol. 19, No.4, pp.529-548, 2013. DOI: 10.1007/s10732-011-9180-4
• M. Xu, Y. Wang, and A. Wei: "Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling", Control Theory and Technology, Vol. 12, No. 2, pp. 187-197, 2014. DOI: 10.1007/s11768-014-0153-7
• J. Yáñez J., J. Ramirez, "The robust coloring problem", European Journal of Operational Research, Vol.148, No.3, pp. 546-558, 2003. DOI: 10.1016/S0377-2217(02)00362-4
• COLOR web site. Available at : http://mat.gsia.cmu.edu/COLOR/ instances.html .
• DIMACS ftp site. Available at : ftp://dimacs.rutgers.edu/pub/ challenge/graph/benchmarks/ .

Identyfikatory

DOI

10.15439/2015F293