A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM
A hybridalgorithm which combines mathematical programming techniques (Kruskal’s algorithm and the strategy of maintaining arc consistency to solve constraint satisfaction problem “CSP”) and heuristic methods (musical composition method and DSATUR) to resolve the robust graph coloring problem (RGCP)...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad de Costa Rica
2016-08-01
|
| Series: | Revista de Matemática: Teoría y Aplicaciones |
| Subjects: | |
| Online Access: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269 |
| _version_ | 1797761437946347520 |
|---|---|
| author | Román Anselmo Mora Gutiérrez Javier Ramírez Rodríguez Eric A. Rincón García Antonin Ponsich Ana Lilia Laureano Cruces |
| author_facet | Román Anselmo Mora Gutiérrez Javier Ramírez Rodríguez Eric A. Rincón García Antonin Ponsich Ana Lilia Laureano Cruces |
| author_sort | Román Anselmo Mora Gutiérrez |
| collection | DOAJ |
| description | A hybridalgorithm which combines mathematical programming techniques (Kruskal’s algorithm and the strategy of maintaining arc consistency to solve constraint satisfaction problem “CSP”) and heuristic methods (musical composition method and DSATUR) to resolve the robust graph coloring problem (RGCP) is proposed in this paper. Experimental result shows that this algorithm is better than the other algorithms presented on the literature. |
| first_indexed | 2024-03-12T19:13:01Z |
| format | Article |
| id | doaj.art-4c60243ea1264322b73ea82071bc0e28 |
| institution | Directory Open Access Journal |
| issn | 2215-3373 |
| language | English |
| last_indexed | 2024-03-12T19:13:01Z |
| publishDate | 2016-08-01 |
| publisher | Universidad de Costa Rica |
| record_format | Article |
| series | Revista de Matemática: Teoría y Aplicaciones |
| spelling | doaj.art-4c60243ea1264322b73ea82071bc0e282023-08-02T05:40:14ZengUniversidad de Costa RicaRevista de Matemática: Teoría y Aplicaciones2215-33732016-08-0123242144410.15517/rmta.v23i2.2526922433A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEMRomán Anselmo Mora Gutiérrez0Javier Ramírez Rodríguez1Eric A. Rincón García2Antonin Ponsich3Ana Lilia Laureano Cruces4Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, Ciudad de México, C.P. 02200, México.Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, Ciudad de México, C.P. 02200, México.Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, Ciudad de México, C.P. 02200, México.Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, Ciudad de México, C.P. 02200, México.Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, Ciudad de México, C.P. 02200, México.A hybridalgorithm which combines mathematical programming techniques (Kruskal’s algorithm and the strategy of maintaining arc consistency to solve constraint satisfaction problem “CSP”) and heuristic methods (musical composition method and DSATUR) to resolve the robust graph coloring problem (RGCP) is proposed in this paper. Experimental result shows that this algorithm is better than the other algorithms presented on the literature.https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269metaheuristicscombinatorial optimizationinteger programming |
| spellingShingle | Román Anselmo Mora Gutiérrez Javier Ramírez Rodríguez Eric A. Rincón García Antonin Ponsich Ana Lilia Laureano Cruces A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM Revista de Matemática: Teoría y Aplicaciones metaheuristics combinatorial optimization integer programming |
| title | A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM |
| title_full | A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM |
| title_fullStr | A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM |
| title_full_unstemmed | A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM |
| title_short | A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM |
| title_sort | hybrid algorithm for the robust graph coloring problem |
| topic | metaheuristics combinatorial optimization integer programming |
| url | https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269 |
| work_keys_str_mv | AT romananselmomoragutierrez ahybridalgorithmfortherobustgraphcoloringproblem AT javierramirezrodriguez ahybridalgorithmfortherobustgraphcoloringproblem AT ericarincongarcia ahybridalgorithmfortherobustgraphcoloringproblem AT antoninponsich ahybridalgorithmfortherobustgraphcoloringproblem AT analilialaureanocruces ahybridalgorithmfortherobustgraphcoloringproblem AT romananselmomoragutierrez hybridalgorithmfortherobustgraphcoloringproblem AT javierramirezrodriguez hybridalgorithmfortherobustgraphcoloringproblem AT ericarincongarcia hybridalgorithmfortherobustgraphcoloringproblem AT antoninponsich hybridalgorithmfortherobustgraphcoloringproblem AT analilialaureanocruces hybridalgorithmfortherobustgraphcoloringproblem |