IEICE TRANSACTIONS on Fundamentals
On the Stack Number and the Queue Number of the Bubble-Sort Graph
Summary :
In this paper, we consider the stack layout of the bubble-sort graph. The bubble-sort graph is a type of Cayley graph on a symmetric group; the bubble-sort graph has an important role for the study of Cayley graphs as interconnection networks. The stack layout and the queue layout problem that are treated in this paper have been studied widely. In this paper, we show that the stack number of the bubble-sort graph BS(n) is either n-1 or n-2. In addition, we show that an upper bound of the queue number of BS(n) is n-2.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1012-1018
- Publication Date
- 2016/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.1012
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Yuuki TANAKA
Faculty of Science and Technology, Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Yuuki TANAKA, "On the Stack Number and the Queue Number of the Bubble-Sort Graph" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1012-1018, June 2016, doi: 10.1587/transfun.E99.A.1012.
Abstract: In this paper, we consider the stack layout of the bubble-sort graph. The bubble-sort graph is a type of Cayley graph on a symmetric group; the bubble-sort graph has an important role for the study of Cayley graphs as interconnection networks. The stack layout and the queue layout problem that are treated in this paper have been studied widely. In this paper, we show that the stack number of the bubble-sort graph BS(n) is either n-1 or n-2. In addition, we show that an upper bound of the queue number of BS(n) is n-2.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1012/_p
Copy
@ARTICLE{e99-a_6_1012,
author={Yuuki TANAKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Stack Number and the Queue Number of the Bubble-Sort Graph},
year={2016},
volume={E99-A},
number={6},
pages={1012-1018},
abstract={In this paper, we consider the stack layout of the bubble-sort graph. The bubble-sort graph is a type of Cayley graph on a symmetric group; the bubble-sort graph has an important role for the study of Cayley graphs as interconnection networks. The stack layout and the queue layout problem that are treated in this paper have been studied widely. In this paper, we show that the stack number of the bubble-sort graph BS(n) is either n-1 or n-2. In addition, we show that an upper bound of the queue number of BS(n) is n-2.},
keywords={},
doi={10.1587/transfun.E99.A.1012},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - On the Stack Number and the Queue Number of the Bubble-Sort Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1012
EP - 1018
AU - Yuuki TANAKA
PY - 2016
DO - 10.1587/transfun.E99.A.1012
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - In this paper, we consider the stack layout of the bubble-sort graph. The bubble-sort graph is a type of Cayley graph on a symmetric group; the bubble-sort graph has an important role for the study of Cayley graphs as interconnection networks. The stack layout and the queue layout problem that are treated in this paper have been studied widely. In this paper, we show that the stack number of the bubble-sort graph BS(n) is either n-1 or n-2. In addition, we show that an upper bound of the queue number of BS(n) is n-2.
ER -
English
