Precedence Thinness of Graphs and Restricted Hamming-Huffman Trees
Authors:
Autores
| Person role | Person | |
|---|---|---|
|
7215 |
1887,6,3155
|
|
|
7214 |
1887,6,3155
|
|
|
7213 |
1887,6,3155
|
Informations:
Pesc publication
Grafos de intervalo e grafos de intervalo próprio são classes de grafos bem conhecidas e para as quais existe uma ampla literatura relacionada. Como consequência, algumas generalizações foram propostas com o passar dos anos, nas quais grafos em geral são expressos por meio de k grafos de intervalo.
Um exemplo recente desse tipo de generalização são as classes dos grafos k-fino e k-fino próprio, que generalizam grafos de intervalo e grafos de intervalo próprio, respectivamente. Neste trabalho, é introduzido uma subclasse dos grafos k-fino (resp. k-fino próprio), chamada de grafos k-fino de precedência (resp. k-fino próprio de precedência). Com relação aos grafos k-fino de precedência particionados, é apresentado um algoritmo polinomial de reconhecimento baseado em árvores PQ. Considerando os grafos k-fino próprio de precedência particionados, é provado que o problema de reconhecimento relacionado é NP-completo para um k arbitrário e polinomial quando k é fixo. Além disso, é apresentado uma caracterização baseada em grafos de limiar para ambas as classes.
Na década de oitenta, Hamming propôs uma estrutura, denominada de árvore Hamming-Huffman (AHH), que une compressão de dados e detecção de erros.
Considerando as AHHs, esta tese define uma versão mais restrita desse tipo de estrutura, denominada [k]-AHH, que admite símbolos em no máximo k níveis distintos. Neste trabalho, é apresentado um algoritmo polinomial para a construção de [2]-AHHs ótimas. Para símbolos com frequências uniformes, é provado que uma AHH ótima é sempre uma [5]-AHH e que sempre existe uma AHH ótima que também é uma [4]-AHH. Por fim, considerando os resultados experimentais, é conjecturado que sempre existe uma AHH uniforme ótima que também é uma [3]-AHH.
Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been proposed, in which graphs in general are expressed in terms of k interval graphs, by splitting the graph in some special way.
As a recent example of such an approach, the classes of k-thin and proper k-thin graphs have been introduced generalizing interval and proper interval graphs, respectively. In this work, we introduce a subclass of k-thin graphs (resp. proper k-thin graphs), called precedence k-thin graphs (resp. precedence proper k-thin graphs). Concerning partitioned precedence k-thin graphs, we present a polynomial time recognition algorithm based on PQ trees. With respect to partitioned precedence proper k-thin graphs, we prove that the related recognition problem is NP-complete for an arbitrary k and polynomial-time solvable when k is fixed. Moreover, we present a characterization for these classes based on threshold graphs.
In the eighties, Hamming proposed a data structure, called Hamming-Huffman tree (HHT), in which both data compression and data error detection are tackled.
Considering Hamming-Huffman trees, we define a restricted version of this structure, called [k]-HHT, which admits symbol leaves in at most k different levels. We present an algorithm to build optimal [2]-HHTs. For uniform frequencies, we prove that an optimal HHT is always a [5]-HHT and that there exists an optimal HHT which is a [4]-HHT. Then, considering experimental results, we conjecture that there exists an optimal uniform tree which is a [3]-HHT.