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
그래프 세분화의 스택-큐 혼합 레이아웃의 한 가지 목표는 스택과 큐의 수가 주어졌을 때 가장자리당 세분화 정점 수가 최소인 레이아웃을 얻는 것입니다. Dujmović와 Wood는 모든 정수에 대해 다음을 보여주었습니다. s, q>0, 모든 그래프 G ~을 가지고있다 s-스택 q-4⌈로그를 사용한 대기열 세분화 레이아웃(s+q)q sn(G)⌉ (각각 2+4⌈log(s+q)q qn(G)⌉) 모서리당 정점 분할, 여기서 sn(G) (관련 qn(G))는 다음의 스택 번호(각각 대기열 번호)입니다. G. 이 논문은 모든 정수에 대해 다음을 보여줌으로써 이러한 결과를 개선합니다. s, q>0, 모든 그래프 G ~을 가지고있다 s-스택 q-최대 2⌈로그를 포함하는 대기열 세분화 레이아웃s+q-1sn(G)⌉ (각각 최대 2⌈logs+q-1qn(G)⌉ +4) 모서리당 분할 정점. 즉, 이 논문은 더 큰 스택 번호 sn(G) 또는 대기열 번호 qn(G) 주어진 정수보다 s and q. 또한, 주어진 정수가 클수록 s 즉, 이 논문이 이전 결과를 더 많이 향상시킵니다.
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.
부
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
부
@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},}
부
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 -