A new upper bound on the queuenumber of hypercubes. (English) Zbl 1231.05190
Discrete Math. 310, No. 4, 935-939 (2010); erratum ibid. 310, No. 13-14, 2059 (2010).
Summary: 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 \(Q_n\) can be laid out using \(n - 3\) queues for \(n\geqslant 8\). Our result improves the previously known result for the case \(n\geqslant 8\).
MSC:
| 05C65 | Hypergraphs |
| 05C35 | Extremal problems in graph theory |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Dujmović, V.; Morin, P.; Wood, D. R., Layout of graphs with bounded tree-width, SIAM J. Comput., 34, 553-579 (2005) · Zbl 1069.05055 |
| [2] | Dujmović, V.; Wood, D. R., On linear layouts of graphs, Discrete Math. Theor. Comput. Sci., 6, 339-358 (2004) · Zbl 1059.05077 |
| [3] | J.L. Ganley, Stack and queue layouts of Halin graphs, 1995, manuscript; J.L. Ganley, Stack and queue layouts of Halin graphs, 1995, manuscript |
| [4] | Hasunuma, T., Queue layouts of iterated line directed graphs, Discrete Appl. Math., 155, 1141-1154 (2007) · Zbl 1117.05046 |
| [5] | Hasunuma, T.; Hirota, M., An improved upper bound on the queuenumber of the hypercube, Inform. Process. Lett., 104, 41-44 (2007) · Zbl 1184.68146 |
| [6] | Heath, L. S.; Leighton, F. T.; Rosenberg, A. L., Comparing queues and stacks as mechanisms for laying out graphs, SIAM J. Discrete Math., 5, 398-412 (1992) · Zbl 0764.05093 |
| [7] | Heath, L. S.; Pemmaraju, S. V., Stack and queue layouts of posets, SIAM J. Discrete Math., 10, 599-625 (1997) · Zbl 0884.05086 |
| [8] | Heath, L. S.; Pemmaraju, S. V.; Trenk, A. N., Stack and queue layouts of directed acyclic graphs: Part I, SIAM J. Comput., 28, 1510-1539 (1999) · Zbl 0926.68095 |
| [9] | Heath, L. S.; Rosenberg, A. L., Laying out graphs using queues, SIAM J. Comput., 21, 927-958 (1992) · Zbl 0778.05078 |
| [10] | Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0743.68007 |
| [11] | Pai, K.-J.; Chang, J.-M.; Wang, Y.-L., A note on “An improved upper bound on the queuenumber of the hypercube”, Inform. Process. Lett., 108, 107-109 (2008) · Zbl 1193.68064 |
| [12] | Rengarajan, S.; Madhavan, C. E., Stack and queue number of 2-trees, (Du, Ding-Zhu; Li, Ming, Proc. 1st Annual International Conf. on Computing and Combinatorics. Proc. 1st Annual International Conf. on Computing and Combinatorics, COCOON’95. Proc. 1st Annual International Conf. on Computing and Combinatorics. Proc. 1st Annual International Conf. on Computing and Combinatorics, COCOON’95, LNCS, vol. 959 (1995), Springer), 203-212 · Zbl 1527.68168 |
| [13] | Rosenberg, A. L., The diogenes approach to testable fault-tolerant arrays of processors, IEEE Trans. Comput., C-32, 902-910 (1983) |
| [14] | Wood, D. R., Queue layouts, tree-width, and three-dimensional graph drawing, (Agrawal, M.; Seth, A., Proc. 22nd Foundations of Software Technology and Theoretical Computer Science. Proc. 22nd Foundations of Software Technology and Theoretical Computer Science, FSTTCS’02. Proc. 22nd Foundations of Software Technology and Theoretical Computer Science. Proc. 22nd Foundations of Software Technology and Theoretical Computer Science, FSTTCS’02, LNCS, vol. 2556 (2002), Springer), 348-359 · Zbl 1027.68647 |
| [15] | Wood, D. R., Queue layouts of graph products and powers, Discrete Math. Theor. Comput. Sci., 7, 255-268 (2005) · Zbl 1153.05325 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
