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
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.
Miki MIYAUCHI
NTT Corporation
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Miki MIYAUCHI, "Topological Stack-Queue Mixed Layouts of Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 2, pp. 510-522, February 2020, doi: 10.1587/transfun.2019EAP1097.
Abstract: One goal in stack-queue mixed layouts of a graph subdivision is to obtain a layout with minimum number of subdivision vertices per edge when the number of stacks and queues are given. Dujmović and Wood showed that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with 4⌈log(s+q)q sn(G)⌉ (resp. 2+4⌈log(s+q)q qn(G)⌉) division vertices per edge, where sn(G) (resp. qn(G)) is the stack number (resp. queue number) of G. This paper improves these results by showing that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with at most 2⌈logs+q-1sn(G)⌉ (resp. at most 2⌈logs+q-1qn(G)⌉ +4) division vertices per edge. That is, this paper improves previous results more, for graphs with larger stack number sn(G) or queue number qn(G) than given integers s and q. Also, the larger the given integer s is, the more this paper improves previous results.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019EAP1097/_p
Copiar
@ARTICLE{e103-a_2_510,
author={Miki MIYAUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Topological Stack-Queue Mixed Layouts of Graphs},
year={2020},
volume={E103-A},
number={2},
pages={510-522},
abstract={One goal in stack-queue mixed layouts of a graph subdivision is to obtain a layout with minimum number of subdivision vertices per edge when the number of stacks and queues are given. Dujmović and Wood showed that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with 4⌈log(s+q)q sn(G)⌉ (resp. 2+4⌈log(s+q)q qn(G)⌉) division vertices per edge, where sn(G) (resp. qn(G)) is the stack number (resp. queue number) of G. This paper improves these results by showing that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with at most 2⌈logs+q-1sn(G)⌉ (resp. at most 2⌈logs+q-1qn(G)⌉ +4) division vertices per edge. That is, this paper improves previous results more, for graphs with larger stack number sn(G) or queue number qn(G) than given integers s and q. Also, the larger the given integer s is, the more this paper improves previous results.},
keywords={},
doi={10.1587/transfun.2019EAP1097},
ISSN={1745-1337},
month={February},}
Copiar
TY - JOUR
TI - Topological Stack-Queue Mixed Layouts of Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 510
EP - 522
AU - Miki MIYAUCHI
PY - 2020
DO - 10.1587/transfun.2019EAP1097
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2020
AB - One goal in stack-queue mixed layouts of a graph subdivision is to obtain a layout with minimum number of subdivision vertices per edge when the number of stacks and queues are given. Dujmović and Wood showed that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with 4⌈log(s+q)q sn(G)⌉ (resp. 2+4⌈log(s+q)q qn(G)⌉) division vertices per edge, where sn(G) (resp. qn(G)) is the stack number (resp. queue number) of G. This paper improves these results by showing that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with at most 2⌈logs+q-1sn(G)⌉ (resp. at most 2⌈logs+q-1qn(G)⌉ +4) division vertices per edge. That is, this paper improves previous results more, for graphs with larger stack number sn(G) or queue number qn(G) than given integers s and q. Also, the larger the given integer s is, the more this paper improves previous results.
ER -