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

Topological Stack-Queue Mixed Layouts of Graphs Layouts mistos de gráficos de fila de pilha topológica

Miki MIYAUCHI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Um objetivo em layouts mistos de fila de pilha de uma subdivisão de grafo é obter um layout com número mínimo de vértices de subdivisão por aresta quando o número de pilhas e filas é fornecido. Dujmović e Wood mostraram que para cada número inteiro s, q>0, cada gráfico G tem um s-pilha q-layout de subdivisão de fila com 4⌈log(s+q)q sn(G)⌉ (resp. 2+4⌈log(s+q)q qn(G)⌉) divisão de vértices por aresta, onde sn(G) (resp. qn(G)) é o número da pilha (resp. número da fila) de G. Este artigo melhora esses resultados mostrando que para cada número inteiro s, q>0, cada gráfico G tem um s-pilha q-layout de subdivisão de fila com no máximo 2⌈logs+q-1sn(G)⌉ (resp. no máximo 2⌈logs+q-1qn(G)⌉ +4) divisão de vértices por aresta. Ou seja, este artigo melhora mais os resultados anteriores, para grafos com maior número de pilha sn(G) ou número da fila qn(G) do que números inteiros dados s e q. Além disso, quanto maior o número inteiro fornecido s é, mais este artigo melhora os resultados anteriores.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.2 pp.510-522
Data de publicação
2020/02/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.2019EAP1097
Tipo de Manuscrito
PAPER
Categoria
Gráficos e Redes

autores

Miki MIYAUCHI
  NTT Corporation

Palavra-chave