Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas

Dado un grafo, el problema de coloreo por listas consiste en asignar a cada nodo un color que pertenezca a una lista predeterminada de colores válidos para ese nodo, de modo que vértices adyacentes no reciban un mismo color y usando la mínima cantidad de colores. Este problema es una generalización...

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: 2022
Materias:
Ciencias Informáticas
Coloreo por listas
Búsqueda con retroceso
NP-difícil
Orden de exploración
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/151928
https://publicaciones.sadio.org.ar/index.php/JAIIO/article/download/356/298
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-151928
record_format dspace
spelling I19-R120-10915-1519282023-04-21T20:03:46Z http://sedici.unlp.edu.ar/handle/10915/151928 https://publicaciones.sadio.org.ar/index.php/JAIIO/article/download/356/298 issn:2451-7496 Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas Taboh, Sebastián Méndez Díaz, Isabel Zabala, Paula 2022-10 2022 2023-04-21T12:30:01Z es Ciencias Informáticas Coloreo por listas Búsqueda con retroceso NP-difícil Orden de exploración Dado un grafo, el problema de coloreo por listas consiste en asignar a cada nodo un color que pertenezca a una lista predeterminada de colores válidos para ese nodo, de modo que vértices adyacentes no reciban un mismo color y usando la mínima cantidad de colores. Este problema es una generalización del problema de coloreo y es NP-difícil incluso para grafos de intervalos [1]. Un enfoque que puede tomarse al tratar de resolver problemas NP-difíciles es diseñar algoritmos de búsqueda con retroceso. En [2], la búsqueda con retroceso se define como “una forma sistemática de iterar por todas las posibles configuraciones del espacio de búsqueda”. Con el fin de evitar un gran esfuerzo computacional al realizar una búsqueda exhaustiva, es fundamental poder aplicar podas que permitan descartar soluciones parciales cuando no pueden ser extendidas a soluciones completas mejores que la mejor encontrada hasta el momento. Además, la eficiencia de estos algoritmos depende fuertemente de las formas en las que se extienden las soluciones en cada paso. En este trabajo proponemos un novedoso algoritmo de búsqueda por retroceso que emplea distintas estrategias inteligentes para explorar el espacio de búsqueda para resolver el problema de coloreo por listas para grafos generales y presentamos los resultados computacionales obtenidos. 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 207-207
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 por listas
Búsqueda con retroceso
NP-difícil
Orden de exploración
spellingShingle Ciencias Informáticas
Coloreo por listas
Búsqueda con retroceso
NP-difícil
Orden de exploración
Taboh, Sebastián
Méndez Díaz, Isabel
Zabala, Paula
Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
topic_facet Ciencias Informáticas
Coloreo por listas
Búsqueda con retroceso
NP-difícil
Orden de exploración
description Dado un grafo, el problema de coloreo por listas consiste en asignar a cada nodo un color que pertenezca a una lista predeterminada de colores válidos para ese nodo, de modo que vértices adyacentes no reciban un mismo color y usando la mínima cantidad de colores. Este problema es una generalización del problema de coloreo y es NP-difícil incluso para grafos de intervalos [1]. Un enfoque que puede tomarse al tratar de resolver problemas NP-difíciles es diseñar algoritmos de búsqueda con retroceso. En [2], la búsqueda con retroceso se define como “una forma sistemática de iterar por todas las posibles configuraciones del espacio de búsqueda”. Con el fin de evitar un gran esfuerzo computacional al realizar una búsqueda exhaustiva, es fundamental poder aplicar podas que permitan descartar soluciones parciales cuando no pueden ser extendidas a soluciones completas mejores que la mejor encontrada hasta el momento. Además, la eficiencia de estos algoritmos depende fuertemente de las formas en las que se extienden las soluciones en cada paso. En este trabajo proponemos un novedoso algoritmo de búsqueda por retroceso que emplea distintas estrategias inteligentes para explorar el espacio de búsqueda para resolver el problema de coloreo por listas para grafos generales y presentamos los resultados computacionales obtenidos.
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 Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
title_short Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
title_full Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
title_fullStr Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
title_full_unstemmed Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
title_sort un algoritmo novedoso de búsqueda con retroceso para coloreo por listas
publishDate 2022
url http://sedici.unlp.edu.ar/handle/10915/151928
https://publicaciones.sadio.org.ar/index.php/JAIIO/article/download/356/298
work_keys_str_mv AT tabohsebastian unalgoritmonovedosodebusquedaconretrocesoparacoloreoporlistas
AT mendezdiazisabel unalgoritmonovedosodebusquedaconretrocesoparacoloreoporlistas
AT zabalapaula unalgoritmonovedosodebusquedaconretrocesoparacoloreoporlistas
_version_ 1765660025203720192

Ejemplares similares