
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On the Stack Number and the Queue Number of the BubbleSort Graph
Yuuki TANAKA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E99A
No.6
pp.10121018 Publication Date: 2016/06/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E99.A.1012 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: bubblesort graph, stack layout, queue layout, book embedding,
Full Text: PDF>>
Summary:
In this paper, we consider the stack layout of the bubblesort graph. The bubblesort graph is a type of Cayley graph on a symmetric group; the bubblesort 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 bubblesort graph BS(n) is either n1 or n2. In addition, we show that an upper bound of the queue number of BS(n) is n2.


