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

Abstract

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.