Queue layouts of hypercubes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10103317" target="_blank" >RIV/00216208:11320/12:10103317 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1137/100813865" target="_blank" >http://dx.doi.org/10.1137/100813865</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/100813865" target="_blank" >10.1137/100813865</a>

Result language
angličtina
Original language name
Queue layouts of hypercubes
Original language description
A queue layout of a graph consists of a linear ordering $sigma$ of its vertices and a partition of its edges into sets, called queues, such that in each set no two edges are nested with respect to $sigma$. We show that the n-dimensional hypercube Qn has a layout into $n-lfloor log_2 n rfloor$ queues for all $n ge 1$. On the other hand, for every $epsilon>0$, every queue layout of Qn has more than $(1/2-epsilon) n-O(1/epsilon)$ queues and, in particular, more than (n-2)/3 queues. This improves previously known upper and lower bounds on the minimal number of queues in a queue layout of Qn. For the lower bound we employ a new technique of out-in representations and contractions which may be of independent interest.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)