CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / O problema do cÃdigo de identificaÃÃo foi introduzido em 1998 por Karpovsky com a finalidade de ajudar no diagnÃstico de falhas em sistemas computacionais com multiprocessadores Desde entÃo o estudo sobre esses cÃdigos e suas variantes tem sido desenvolvido Antoine Lobstein mantÃm uma bibliografia com mais de 200 artigos sobre o assunto A ideia do problema consiste em identificar qualquer vÃrtice do grafo utilizando apenas o seu conjunto de identificaÃÃo que sÃo os vÃrtices de sua vizinhanÃa fechada que estÃo no cÃdigo de identificaÃÃo
Muitos estudos recentes se concentraram em grafos infinitos e com isso o objetivo à obter cÃdigos de identificaÃÃo nesses grafos infinitos com a menor densidade possÃvel Em 2005 Ben-Haim e Litsyn provaram que a densidade de um cÃdigo de identificaÃÃo Ãtimo da grade retangular infinita à 7/20. Nessa dissertaÃÃo fazemos um estudo bibliogrÃfico apresentando vÃrios resultados existentes e fornecemos uma prova alternativa para a densidade 7/20 de cÃdigos Ãtimos em grades retangulares infinitas usando o mÃtodo da descarga / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:8970 |
| Date | 16 July 2014 |
| Creators | Rennan Ferreira Dantas |
| Contributors | Rudini Menezes Sampaio, Victor Almeida Campos, Ana Shirley Ferreira da Silva, Mitre Costa Dourado |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds