Conjuntos independentes de vizinhança mínima no b-cubo

• Ano de defesa: 2015
• Autor(a) principal: Sampaio Júnior, Moysés da Silva
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; BR; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Cliques; Minimum neighborhood; Hypercube; Hamming-Huffman; Vizinhança mínima; Hipercubo; Grafos - Teoria; Algoritmos; Compressão de dados - Computação; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/7710

Neste trabalho abordamos o problema onde, dado um par de inteiros positivos l e b, deseja-se encontrar um conjunto independente L com [L] = l nós no grafo b-cubo Qb, tal que L possua uma vizinhança com cardinalidade mínima Opt(b; l). O interesse neste problema surgiu através do estudo inicial de árvores Hamming-Huffman, que visam a integração entre compactação de dados e detecção de erros, no contexto de transmissão de dados. A criação desta árvore um problema em aberto que parece estar diretamente relacionado com vizinhanças em Qb. Na busca de uma solução eficiente para o problema de mínimos um grafo especial, Q2b, cujas cliques tiveram diversas propriedades determinadas e que foram base para dois algoritmos polinomiais em ` e b. Esses algoritmos determinam um conjunto independente L 2 V (Qb), [L] = l, de V (Qb) com vizinhança N(L) de tamanho [N(L)] = v(b; l) maior que Opt(b; l) que conjecturamos ser uma solução para esse problema