DACyTAr - Datos Primarios en Acceso Abierto de la Ciencia y la Tecnología Argentina
Appendix and source code of ACP solver for the paper On the additive chromatic number of several families of graphs
Registro completo
- Título
- Appendix and source code of ACP solver for the paper On the additive chromatic number of several families of graphs
- Autor(es)
- Severín, Daniel Esteban
- Afiliación(es) del/de los autor(es)
-
Severín, Daniel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Rosario; Argentina
- Resumen
-
This folder contains a source code for solving the ADDITIVE COLORING PROBLEM as well as testing the ADDITIVE COLORING CONJECTURE. In addition, it contains the appendix of the paper "On the additive chromatic number of several families of graphs" with proofs of some propositions, the integer programming model and some computational experiments.
Steps to reproduce The programs ACOPT, TEST and DSATUR should be compiled with Visual Studio 2013. The programs also require IBM ILOG CPLEX 12.6. Below, some examples are given. Testing the additive coloring conjecture on all graphs of 4 vertices: test.exe graphs4.all Recall that acopt.exe and dsatur.exe must be present in the same folder. Also, acopt must be compiled without "VERBOSE" definition (just comment that line in source code). Since "test" generates several files on-the-fly and makes heavy use of the hard disk, it is advisable to execute it on a RamDisk. Obtaining the additive chromatic number of a graph, e.g. the cycle sun with m = 10, and assuming an upper bound UB = 8: acopt.exe CS10.graph 8 If none upper bound is provided, it uses UB = Delta(G)^2-Delta(G)+1 by default (which is really bad!). A lower bound LB can also be provided together with UB. For example: acopt.exe KS10.graph 10 4 In particular, for obtaining an additive k-coloring for a specific k, use UB = LB = k. It is recommended to compile acopt with "VERBOSE" definition for viewing log and optimal solution.
This work was partially supported by grants PID-ING 416 (UNR), PICT-2013-0586 (MINCyT) and PIP 11220120100277 (CONICET)
- Año de publicación
- Idioma
-
inglés
- Formato (Tipo MIME)
-
application/octet-stream
application/pdf
- Clasificación temática de acuerdo a la FORD
- Matemáticas
- Materia
- Additive chromatic number; Additive coloring conjecture; Lucky labeling; Graph algorithms; Integer Programming;
- Condiciones de uso
-
bajo licencia Creative Commons https://creativecommons.org/licenses/by/4.0/
Autor
Disponible en acceso abierto
- Repositorio digital
- RepHipUNR (UNR) - Universidad Nacional de Rosario
- Identificador alternativo
- https://doi.org/10.17632/9zwm2nxvbs.1
- Identificador alternativo
- https://doi.org/10.1016/j.ipl.2020.105937
Citación
Severín, Daniel Esteban (): Appendix and source code of ACP solver for the paper On the additive chromatic number of several families of graphs. Universidad Nacional de Rosario, http://hdl.handle.net/2133/18976.