Queue Layouts of Graph Products and Powers

David R. Wood

doi:10.46298/dmtcs.352

David R. Wood - Queue Layouts of Graph Products and Powers

dmtcs:352 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 - https://doi.org/10.46298/dmtcs.352

Queue Layouts of Graph Products and PowersArticle

Authors: David R. Wood ¹

1 Departament de Matemàtica Aplicada II

A \emphk-queue layout of a graph G consists of a linear order σ of V(G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ . This paper studies queue layouts of graph products and powers

https://doi.org/10.46298/dmtcs.352

Source: HAL:hal-00959041v1

Volume: Vol. 7

Published on: January 1, 2005

Imported on: March 26, 2015

Keywords: Hamming graph,graph,queue layout,cartesian product,d-dimensional grid graph,d-dimensional toroidal grid graph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Bibliographic References

10 Documents citing this article

Petr Hlineny;Adam Straka, arXiv (Cornell University), Stack and Queue Numbers of Graphs Revisited, pp. 601-606, 2023, Prague, Czech Republic, 10.5817/cz.muni.eurocomb23-083, https://arxiv.org/abs/2303.10116.

Vida Dujmovic;Gwenael Joret;Piotr Micek;Pat Morin;Torsten Ueckerdt;et al., Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles), Planar Graphs have Bounded Queue-Number, pp. 862-875, 2019, Baltimore, MD, USA, 10.1109/focs.2019.00056, https://dipot.ulb.ac.be/dspace/bitstream/2013/298588/3/1904.04791.pdf.

Kung-Jui PAI;Jou-Ming CHANG;Yue-Li WANG;Ro-Yu WU, 2014, Queue Layouts of Toroidal Grids, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E97.A, 6, pp. 1180-1186, 10.1587/transfun.e97.a.1180.

Vida Dujmović, 2014, Graph layouts via layered separators, Journal of Combinatorial Theory Series B, 110, pp. 79-89, 10.1016/j.jctb.2014.07.005, https://doi.org/10.1016/j.jctb.2014.07.005.

Martin Milanič;Oliver Schaudt, 2013, Computing square roots of trivially perfect and threshold graphs, Discrete Applied Mathematics, 161, 10-11, pp. 1538-1545, 10.1016/j.dam.2012.12.027, https://doi.org/10.1016/j.dam.2012.12.027.

Petr Gregor;Riste Škrekovski;Vida Vukašinović, 2011, On the queue-number of the hypercube, Electronic Notes in Discrete Mathematics, 38, pp. 413-418, 10.1016/j.endm.2011.09.067.

Kung-Jui Pai;Jou-Ming Chang;Yue-Li Wang, 2010, Erratum to “A new upper bound on the queuenumber of hypercubes” [Discrete Math. 310 (2010) 935–939], Discrete Mathematics, 310, 13-14, pp. 2059, 10.1016/j.disc.2010.02.002, https://doi.org/10.1016/j.disc.2010.02.002.

Kung-Jui Pai;Jou-Ming Chang;Yue-Li Wang, 2009, A new upper bound on the queuenumber of hypercubes, Discrete Mathematics, 310, 4, pp. 935-939, 10.1016/j.disc.2009.09.007.

Kung-Jui Pai;Jou-Ming Chang;Yue-Li Wang, 2009, Upper bounds on the queuenumber of k-ary n-cubes, Information Processing Letters, 110, 2, pp. 50-56, 10.1016/j.ipl.2009.10.006.

Toru Hasunuma;Misa Hirota, 2007, An improved upper bound on the queuenumber of the hypercube, Information Processing Letters, 104, 2, pp. 41-44, 10.1016/j.ipl.2007.05.006.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 470 times.

This article's PDF has been downloaded 551 times.