Códigos para Subfamílias de Grafos Cordais
Autores
|
4078 |
877,303,1815
|
|
|
4079 |
877,303,1815
|
|
|
4080 |
877,303,1815
|
Informações:
Publicações do PESC
Este trabalho trata da codificação e do estudo de propriedades estruturais de subfamílias dos grafos cordais. São propostos códigos específicos para os grafos k-caminho e para as k-árvores. Estes códigos são mais compactos do que a representação tradicional por arestas e utilizam algoritmos lineares para codificação e decodificação.
A codificação proposta para os grafos k-caminho viabiliza a obtenção de diversas propriedades estruturais da família. Estas propriedades são fundamentais para a contagem e a geração uniforme de exemplares, bem como para a obtenção de soluções eficientes de problemas tais como o isomorfismo e a determinação do caminho hamiltoniano, problemas estes resolvidos com complexidade O(n).
Utilizando a codificação proposta para as k-árvores, são obtidos algoritmos, também com complexidade O(n), para determinar a coloração ótima de vértices e a seqüência de multiplicidades, conceito que generaliza a seqüência de graus do grafo.
Finalizando, uma nova subfamília dos grafos de intervalo é definida e são delimitadas precisamente as interseções entre diversas subfamílias das k-árvores e dos grafos de intervalo.
This work presents codes and structural properties of subfamilies of chordal graphs. Particular codes for k-path graphs and k-trees are defined. Both codes are more compact than the traditional representation based on edges; linear time algorithms for encoding and decoding are presented.
The code for k-path graphs emphasizes some structural properties of the family. These properties are used for counting and generating instances uniformly. The isomorphism problem and the determination of a hamiltonian path are solved by algorithms with O(n) complexity.
For k-trees, the proposed code allows the development of algorithms, also with O(n) complexity, to determine an optimal coloring of the vertices and the sequence of multiplicities, a new concept that generalizes the sequence of degrees.
Finally, a new subfamily of the interval graphs is defined and the exact intersection among some subfamilies of k-trees and interval graphs are established.