Una comparación de modelos para un nuevo problema de coloreo

El problema de coloreo de vértices consiste en asignar un color a cada vértice de un grafo tal que vértices adyacentes reciban colores distintos, utilizando la mínima cantidad de colores. Este problema ha sido ampliamente estudiado. En este trabajo, presentamos un problema al que llamamos “Problema...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Taboh, Sebastián, Méndez-Díaz, Isabel, Zabala, Paula
Formato:	Objeto de conferencia Resumen
Lenguaje:	Español
Publicado:	2023
Materias:	Ciencias Informáticas coloreo de vértices por componentes conexas modelos de programación matemática heurísticas
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/166482
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-166482
record_format	dspace
spelling	I19-R120-10915-1664822024-05-28T20:08:57Z http://sedici.unlp.edu.ar/handle/10915/166482 Una comparación de modelos para un nuevo problema de coloreo Taboh, Sebastián Méndez-Díaz, Isabel Zabala, Paula 2023-09 2023 2024-05-28T14:48:57Z es Ciencias Informáticas coloreo de vértices por componentes conexas modelos de programación matemática heurísticas El problema de coloreo de vértices consiste en asignar un color a cada vértice de un grafo tal que vértices adyacentes reciban colores distintos, utilizando la mínima cantidad de colores. Este problema ha sido ampliamente estudiado. En este trabajo, presentamos un problema al que llamamos “Problema de Coloreo de Vértices por Componentes Conexas” (CCCP, por sus siglas en inglés), que es una variación del problema de coloreo de vértices y que, hasta donde sabemos, no ha sido definido ni estudiado previamente. Después de demostrar varias propiedades, formalizamos su definición con 3 modelos de programación matemática. Obtenemos también cotas inferiores y superiores, que nos permiten eliminar variables de los modelos originales. Además, diseñamos varias heurísticas para CCCP que permiten obtener soluciones iniciales. Para comparar los rendimientos de los algoritmos basados en los modelos propuestos, tanto respecto a la calidad de las soluciones encontradas así como a los tiempos de ejecución, generamos un conjunto de instancias y llevamos a cabo experimentación. Las conclusiones nos permiten comprender qué partes del algoritmo deberíamos mejorar y también concebir nuevas formas de tratar nuestro problema. Sociedad Argentina de Informática e Investigación Operativa Objeto de conferencia Resumen http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 161-161
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Español
topic	Ciencias Informáticas coloreo de vértices por componentes conexas modelos de programación matemática heurísticas
spellingShingle	Ciencias Informáticas coloreo de vértices por componentes conexas modelos de programación matemática heurísticas Taboh, Sebastián Méndez-Díaz, Isabel Zabala, Paula Una comparación de modelos para un nuevo problema de coloreo
topic_facet	Ciencias Informáticas coloreo de vértices por componentes conexas modelos de programación matemática heurísticas
description	El problema de coloreo de vértices consiste en asignar un color a cada vértice de un grafo tal que vértices adyacentes reciban colores distintos, utilizando la mínima cantidad de colores. Este problema ha sido ampliamente estudiado. En este trabajo, presentamos un problema al que llamamos “Problema de Coloreo de Vértices por Componentes Conexas” (CCCP, por sus siglas en inglés), que es una variación del problema de coloreo de vértices y que, hasta donde sabemos, no ha sido definido ni estudiado previamente. Después de demostrar varias propiedades, formalizamos su definición con 3 modelos de programación matemática. Obtenemos también cotas inferiores y superiores, que nos permiten eliminar variables de los modelos originales. Además, diseñamos varias heurísticas para CCCP que permiten obtener soluciones iniciales. Para comparar los rendimientos de los algoritmos basados en los modelos propuestos, tanto respecto a la calidad de las soluciones encontradas así como a los tiempos de ejecución, generamos un conjunto de instancias y llevamos a cabo experimentación. Las conclusiones nos permiten comprender qué partes del algoritmo deberíamos mejorar y también concebir nuevas formas de tratar nuestro problema.
format	Objeto de conferencia Resumen
author	Taboh, Sebastián Méndez-Díaz, Isabel Zabala, Paula
author_facet	Taboh, Sebastián Méndez-Díaz, Isabel Zabala, Paula
author_sort	Taboh, Sebastián
title	Una comparación de modelos para un nuevo problema de coloreo
title_short	Una comparación de modelos para un nuevo problema de coloreo
title_full	Una comparación de modelos para un nuevo problema de coloreo
title_fullStr	Una comparación de modelos para un nuevo problema de coloreo
title_full_unstemmed	Una comparación de modelos para un nuevo problema de coloreo
title_sort	una comparación de modelos para un nuevo problema de coloreo
publishDate	2023
url	http://sedici.unlp.edu.ar/handle/10915/166482
work_keys_str_mv	AT tabohsebastian unacomparaciondemodelosparaunnuevoproblemadecoloreo AT mendezdiazisabel unacomparaciondemodelosparaunnuevoproblemadecoloreo AT zabalapaula unacomparaciondemodelosparaunnuevoproblemadecoloreo
_version_	1807223041862664192

Una comparación de modelos para un nuevo problema de coloreo

Ejemplares similares