Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The packing radius of a code and partitioning problems: The case for poset metrics on finite vector spaces

Texto completo
Autor(es):
Lucas D'Oliveira, Rafael Gregorio [1] ; Firer, Marcelo [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, IMECC UNICAMP, BR-13083859 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: DISCRETE MATHEMATICS; v. 338, n. 12, p. 2143-2167, DEC 6 2015.
Citações Web of Science: 8
Resumo

Until this work, the packing radius of a poset code was only known in the cases where the poset was a chain, a hierarchy, a union of disjoint chains of the same size, and for some families of codes. Our objective is to approach the general case of any poset. To do this, we will divide the problem into two parts. The first part consists in finding the packing radius of a single vector. We will show that this is equivalent to a generalization of a well known NP-hard problem known as ``the partition problem{''}. Then, we will review the main results known about this problem giving special attention to the algorithms to solve it. The main ingredient to these algorithms is what is known as the differentiating method, which we will extend to the general case. The second part consists in finding the vector that determines the packing radius of the code. For this, we will show how it is sometimes possible to compare the packing radius of two vectors without calculating them explicitly. (C) 2015 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 13/25977-7 - Segurança e confiabilidade da informação: teoria e prática
Beneficiário:Marcelo Firer
Linha de fomento: Auxílio à Pesquisa - Temático