Problemas de código de identificação em grades

• Ano de defesa: 2014
• Autor(a) principal: Dantas, Rennan Ferreira
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Ciência da computação; Códigos de identificação; Grade triangular; Grade quadrada; Grade infinita; Identifying codes
• Link de acesso: http://www.repositorio.ufc.br/handle/riufc/18555

The identifying code problem was introduced in 1998 by Karpovsky as a way to help fault diagnosis in multiprocessor computer systems Since then the study of this problem and its variants has been developed Antoine Lobstein maintains a bibliography with more than 200 articles on this subject The idea of the problem is to identify any vertex of the graph using just its identifying set which are the vertices of its closed neighborhood in the identifying code Many recent papers have investigated infinite graphs and then the main objective is to obtain identifying codes in these infinite graphs with the smallest possible density In 2005 Ben-Haim and Litsyn proved that the density of an optimum identifying code in the infinite rectangular grid is 7/20 In this dissertation we present a bibliographical study showing several existing results and we provide an alternative proof to the density 7/20 for optimum identifying codes in infinite rectangular grids using the discharging method.