EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 59 / No 6 (November-December 2025) RAIRO-Oper. Res., 59 6 (2025) 3621-3648 References
Open Access
Issue
RAIRO-Oper. Res.
Volume 59, Number 6, November-December 2025
Page(s) 3621 - 3648
DOI https://doi.org/10.1051/ro/2025140
Published online 08 December 2025
  • F. Bonomo and M. Valencia-Pabon, Minimum sum coloring of p4-sparse graphs. Electron. Notes Discrete Math. 35 (2009) 293–298. [Google Scholar]
  • F. Bonomo and M. Valencia-Pabon, On the minimum sum coloring of p4-sparse graphs. Graphs Comb. 30 (2012) 303–314. [Google Scholar]
  • F. Bonomo, G. Duran, A. Napoli and M. Valencia-Pabon, A one-to-one correspondence between potential solutions ofthe cluster deletion problem and the minimum sum coloring problem, and its application to p4-sparse graphs. Inf. Process. Lett. 115 (2015) 600–603. [Google Scholar]
  • A. Borodin, I. Ivan, Y. Ye and B. Zimny, On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418 (2012) 1–13. [Google Scholar]
  • Y. Boudabbous and P. Illel, Indecomposability graph and critical vertices of an indecomposable graph. Discrete Math. 309 (2009) 2839–2846. [Google Scholar]
  • H. Bouziri and M. Jouini, A tabu search approach for the sum coloring problem. Electron. Notes Discrete Math. 36 (2010) 915–922. [Google Scholar]
  • B.G. Dantzig, Linear Programming and Extensions. Princeton University Press (1963). [Google Scholar]
  • I. DeHaan and Z. Friggstad, Approximate minimum sum colorings and maximum k-colorable subgraphs of chordal graphs, in Algorithms and Data Structures. 18th International Symposium, WADS 2023. Vol. 14079 of Lecture Notes in Computer Science, edited by P. Morin and S. Suri. Springer, New York, NY (2023) 627–639. [Google Scholar]
  • D. Delle Donne, F. Furini, E. Malaguti and R.W. Calvo, A branch-and-price algorithm for the minimum sum coloring problem. Discrete Appl. Math. 303 (2021) 39–56. [Google Scholar]
  • M.J. Dinneen, A. Mahasinghe and K. Liu, Finding the chromatic sums of graphs using a d-wave quantum computer. J. Supercomput. 75 (2019) 4811–4828. [Google Scholar]
  • E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Program. 91 (2002) 201–213. [Google Scholar]
  • S.M. Douiri and S. Elbernoussi, New algorithm for the sum coloring problem. Int. J. Contemp. Math. Sci. 6 (2011) 453–463. [Google Scholar]
  • S.M. Douiri and S. Elbernoussi, A new ant colony optimization algorithm for the lower bound of sum coloring problem. J. Math. Modell. Algorithms 11 (2012) 181–192. [Google Scholar]
  • L. Epstein and A. Levin, On the performance guarantee of first fit for sum coloring. J. Comput. Syst. Sci. 99 (2019) 91–105. [Google Scholar]
  • F. Furini, E. Malaguti, S. Martin and I.-C. Ternier, ILP models and column generation for the minimum sum coloring problem. Electron. Notes Discrete Math. 64 (2018) 215–224. [Google Scholar]
  • M. Habib and C. Paul, A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4 (2010) 41–59. [Google Scholar]
  • M. Habib, R.M. McConnell, C. Paul and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234 (2000) 59–84. [Google Scholar]
  • H. Hajiabolhassan, M.L. Mehrabadiy and R. Tusserkani, Note minimal coloring and strength of graphs. Discrete Math. 215 (2000) 265–270. [Google Scholar]
  • O. Harrabi and J. Chaouachi, Towards effective resolution approaches for solving the sum coloring problem. J. Exper. Theor. Artif. Intell. 32 (2020) 31–57. [Google Scholar]
  • O. Harrabi and J. Chaouachi Siala, An effective parameter tuning for a bi-objective genetic algorithm to solve the sum coloring problem, in Soft Computing for Problem Solving. Vol. 816 of Advances in Intelligent Systems and Computing, edited by J.C. Bansal, K.N. Das, A. Nagar, K. Deep and A.K. Ojha. Springer, New York, NY (2017) 107–120. [Google Scholar]
  • O. Harrabi and J. Chaouachi Siala, A new sum coloring-based integer linear programming for solving the university course timetabling problem, in 2020 International Multi-Conference on: “Organization of Knowledge and Advanced Technologies” (OCTA) (2020) 1–2. [Google Scholar]
  • O. Harrabi and J. Chaouachi Siala, A novel unfeasible space exploring matheuristic proposal to solve the sum coloring problem, in Advances in Computational Collective Intelligence. 14th International Conference, ICCCI 2022. Vol. 1653 of Communications in Computer and Information Science, edited by C. Bădiă, J. Treur, D. Benslimane, B. Hnatkowska and M. Krótkiewicz. Springer, New York, NY (2022) 627–639. [Google Scholar]
  • O. Harrabi, J. Chaouachi Siala and H. Bouziri, On solving exactly and approximately the sum coloring of graphs, in Proceedings. 2017 IEEE/ACS 14th International Conference on Computer Systems and Applications. Hammamet, Tunisia. IEEE Computer Society, CPS (2017) 1043–1048. [Google Scholar]
  • O. Harrabi, E. Fatnassi, H. Bouziri and J. Chaouachi Siala, A bi-objective memetic algorithm proposal for solving the minimum sum coloring problem, in GECCO ’17: Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM SIGEVO, Association for Computing Machinery, New York, NY (2017) 27–28. [Google Scholar]
  • O. Harrabi, J. Chaouachi Siala and H. Bouziri, On integrating an iterated variable neighborhood search within a bi-objective genetic algorithm: sum coloring of graphs case application. Electron. Notes Discrete Math. 66 (2018) 55–62. [Google Scholar]
  • Y. Jin and J.-K. Hao, Hybrid evolutionary search for the minimum sum coloring problem of graphs. Inf. Sci. 352, 353 (2016) 15–34. [Google Scholar]
  • Y. Jin, J.-K. Hao and J.-P. Hamiez, A memetic algorithm for the minimum sum coloring problem. Comput. Oper. Res. 43 (2014) 318–327. [Google Scholar]
  • E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, in Proceedings of the 17th AC Mannual computer science conference. USA, New York, NY (1989) 39–45. [Google Scholar]
  • C. Lecat, C. Lucet and C.M. Li, Sum coloring: new upper bounds for the chromatic strength. Discrete Appl. Math. 233 (2017) 71–82. [Google Scholar]
  • W. Lin, M. Xiao, Y. Zhou and Z. Guo, Computing lower bounds for minimum sum coloring and optimum cost chromatic partition. Comput. Oper. Res. 109 (2019) 263–272. [Google Scholar]
  • M. Malafiejsk, K. Giaro, R. Janczewski and M. Kubale, Sum coloring of bipartite graphs with bounded degree. Algorithmica 40 (2004) 235–244. [Google Scholar]
  • M. Minot, S.N. Ndiaye and C. Solnon, Évaluation d’approches complètes pour le problème de somme coloration, in Douzièmes Journées Francophones de Programmation par Contraintes, JFPC, edited by P. Vismara and E. Hebrard. SupAgro, LIRMM, Montpellier, Montepelier, France (2016) 53–62. [Google Scholar]
  • A. Moukrim, K. Sghiouer, Y. Li and C. Lucet, Lower bounds for the minimal sum coloring problem. Electron. Notes Discrete Math. 36 (2010) 663–670. [Google Scholar]
  • M. Mrad, O. Harrabi, J. Chaouachi Siala and A. Gharbi, A column generation-based lower bound for the minimum sum coloring problem. IEEE Access 8 (2020) 57891–57904. [Google Scholar]
  • S. Nicoloso, M. Sarrafzadeh and X. Song, On the sum coloring problem on interval graphs. Algorithmica 23 (1999) 109–126. [Google Scholar]
  • S.D. Nikolopoulos, L. Palios and C. Papadopoulos, A fully dynamic algorithm for the recognition of p4-sparse graphs. Theor. Comput. Sci. 439 (2012) 41–57. [Google Scholar]
  • C. Paul, Aspects Algorithmiques de la décomposition modulaire. Habilitation à diriger des recherches, CNRS – LIRMM – Montpellier 2 University, Montpellier, France (2006). Available at https://theses.hal.science/tel-00112390/document. [Google Scholar]
  • M. Rao, Décompositions de graphes et algorithmes efficaces. PhD thesis, Paul Verlaine University, Metz, France (2006). Available at https://hal.univ-lorraine.fr/tel-01752468. [Google Scholar]
  • M.R. Salavatipour, On sum coloring of graphs. Discrete Appl. Math. 127 (2003) 477–488. [Google Scholar]
  • A. Sen, A. Deng and S. Guha, On a graph partition problem with application to vlsi layout. Inf. Process. Lett. 43 (1992) 87–94. [Google Scholar]
  • J. Spinard, P4-trees and substitution decomposition. Discrete Appl. Math. 39 (1992) 263–291. [Google Scholar]
  • T. Szkaliczki, Routing with minimum wire length in the dogleg-free manhattan model is np-complete. SIAM J. Comput. 29 (1999) 274–287. [Google Scholar]
  • M. Tedder, D. Corneil, M. Habib and C. Paul, Simpler linear-time modular decomposition via recursive factorizing permutations, in Automata, Languages and Programming, edited by L. Aceto, I. Damgård, L.A. Goldberg, M.M. Halldórsson, A. Ingólfsdóttir and I. Walukiewicz. Springer Berlin Heidelberg, Berlin, Heidelberg (2008) 634–645. [Google Scholar]
  • Q. Wu and J.-K. Hao, An effective heuristic algorithm for sum coloring of graphs. Comput. Oper. Res. 39 (2012) 1593–1600. [Google Scholar]
  • Q. Wu, Q. Zhou, Y. Jin and J.-K. Hao, Minimum sum coloring for large graphs with extraction andbackward expansion search. Appl. Soft Comput. 62 (2018) 1056–1065. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.