A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Huffman Tree Problem with Upper-Bounded Linear Functions O problema da árvore de Huffman com funções lineares com limite superior

Hiroshi FUJIWARA, Yuichi SHIRAI, Hiroaki YAMAMOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

A construção de um código de Huffman pode ser entendida como o problema de encontrar uma árvore binária completa tal que cada folha esteja associada a uma função linear da profundidade da folha e a soma dos valores da função seja minimizada. Fujiwara e Jacobs estenderam isso para uma função geral e provaram que o problema estendido era NP-difícil. Os autores também mostraram o caso em que as funções associadas às folhas são não decrescentes e convexas podem ser resolvidas em tempo polinomial. No entanto, a complexidade do caso de funções não convexas não decrescentes permanece desconhecida. Neste artigo, tentamos revelar a complexidade considerando funções não decrescentes e não convexas, cada uma das quais assume o menor valor de uma função linear ou de uma constante. Como resultado, fornecemos um algoritmo de tempo polinomial para duas subclasses de tais funções.

Publicação
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.474-480
Data de publicação
2022/03/01
Publicitada
2021/10/12
ISSN online
1745-1361
DOI
10.1587/transinf.2021FCP0006
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
Categoria

autores

Hiroshi FUJIWARA
  Shinshu University
Yuichi SHIRAI
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

Palavra-chave