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

Minimum Congestion Embedding of Complete Binary Trees into Tori Incorporação mínima de congestionamento de árvores binárias completas no Tori

Akira MATSUBAYASHI, Ryo TAKASU

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Consideramos o problema de incorporar árvores binárias completas em toros bidimensionais com congestionamento mínimo (borda). Sabe-se que para um número inteiro positivo n, Um 2nA árvore binária completa de -1 vértice pode ser incorporada em um (2n / 2+ 1)(2n / 2+1)-grade e um 2n / 2 2n / 2-grid com congestionamento 1 e 2, respectivamente. No entanto, não se sabe se 2nA árvore binária completa -1-vértice pode ser incorporada em um 2n / 2 2n / 2-grade com congestionamento de unidade. Neste artigo, mostramos que uma resposta positiva pode ser obtida adicionando arestas envolventes às grades, ou seja, um 2nA árvore binária completa de -1 vértice pode ser incorporada com congestionamento de unidade em um 2n / 2 2n / 2-toro. A incorporação aqui proposta atinge o congestionamento mínimo e um tamanho quase mínimo de um toro (até o termo constante de 1). Em particular, a incorporação é ideal para o problema de incorporação de um 2n-1-vértice árvore binária completa com um número inteiro par n em um toro quadrado com congestionamento unitário.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.9 pp.1804-1808
Data de publicação
2000/09/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Gráficos e Redes

autores

Palavra-chave