A new upper bound on the queuenumber of hypercubes |
| |
Authors: | Kung-Jui Pai Jou-Ming Chang |
| |
Institution: | a Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC b Institute of Information Science and Management, National Taipei College of Business, Taipei, Taiwan, ROC c Department of Industrial Engineering and Management, Mingchi University of Technology, Taipei County, Taiwan, ROC |
| |
Abstract: | A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. In this paper, we show that the n-dimensional hypercube Qn can be laid out using n−3 queues for n?8. Our result improves the previously known result for the case n?8. |
| |
Keywords: | Combinatorial problems Queue layout Hypercube Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|