Experimentos computacionales en la resolución del problema de códigos de identificación

El Problema de Códigos de Identificación (PCI) es un problema NP-difícil relativamente nuevo que, además de contar con aplicaciones concretas (véase el trabajo de Karpovsky, Chakrabarty y Levitin, On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory 44, 599–611), es de...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Severin, D., Vansteenkiste, V.
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2015
Materias:
Ciencias Informáticas
modelo de programación entera
códigos de identificación
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/59305
http://44jaiio.sadio.org.ar/sites/default/files/sio15-15.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-59305
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
modelo de programación entera
códigos de identificación
spellingShingle Ciencias Informáticas
modelo de programación entera
códigos de identificación
Severin, D.
Vansteenkiste, V.
Experimentos computacionales en la resolución del problema de códigos de identificación
topic_facet Ciencias Informáticas
modelo de programación entera
códigos de identificación
description El Problema de Códigos de Identificación (PCI) es un problema NP-difícil relativamente nuevo que, además de contar con aplicaciones concretas (véase el trabajo de Karpovsky, Chakrabarty y Levitin, On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory 44, 599–611), es desafiante tanto desde el punto de vista teórico como computacional. En particular, se han propuesto algoritmos polinomiales para resolver el PCI sobre clases particulares de grafos y, más recientemente, se ha estudiado el poliedro asociado a su formulación natural donde, en algunos casos, se ha dado la descripción completa para algunas familias de grafos (véase el trabajo de Argiroffo, Bianchi y Wagler, Study of Identifying Code Polyhedra for Some Families of Split Graphs, LNCS 8596, 13–25). En esta comunicación reportamos algunos experimentos computacionales respecto a la performance de un modelo de programación entera para el PCI.
format Objeto de conferencia
Resumen
author Severin, D.
Vansteenkiste, V.
author_facet Severin, D.
Vansteenkiste, V.
author_sort Severin, D.
title Experimentos computacionales en la resolución del problema de códigos de identificación
title_short Experimentos computacionales en la resolución del problema de códigos de identificación
title_full Experimentos computacionales en la resolución del problema de códigos de identificación
title_fullStr Experimentos computacionales en la resolución del problema de códigos de identificación
title_full_unstemmed Experimentos computacionales en la resolución del problema de códigos de identificación
title_sort experimentos computacionales en la resolución del problema de códigos de identificación
publishDate 2015
url http://sedici.unlp.edu.ar/handle/10915/59305
http://44jaiio.sadio.org.ar/sites/default/files/sio15-15.pdf
work_keys_str_mv AT severind experimentoscomputacionalesenlaresoluciondelproblemadecodigosdeidentificacion
AT vansteenkistev experimentoscomputacionalesenlaresoluciondelproblemadecodigosdeidentificacion
bdutipo_str Repositorios
_version_ 1764820478371823618

Ejemplares similares