Stack and Queue Layouts for Toruses and Extended Hypercubes

Simple item page
dc.contributor.authorBettayeb, Said
dc.date.accessioned2020-05-08T16:32:40Z
dc.date.available2020-05-08T16:32:40Z
dc.date.issued2010
dc.description.abstractLinear layouts play an important role in many applications including networks and VLSI design. Stack and queue layouts are two important types of linear layouts. We consider the stack number, s(G), and queue number, q(G), for multidimensional k-ary hypercubes and toruses. Heath, Leighton, and Rosenberg showed that d-dimensional ternary hypercubes have stack number ¿,(N 1/9 ), with N=3 d nodes. Malitz showed that E edges implies stack number O(¿E). For k-ary d-dimensional hypercubes, with N = k d vertices, Malitz's bound is O(k d/2 ). We improve this to 2 d+1 -3. The 2 d+1 -3 bound holds for arbitrary d-dimensional toruses. The queue number of d-dimensional k-ary hypercubes or toruses is bounded by O(d). Hence, Heath, Leighton, and Rosenberg exhibit an exponential tradeoff between s(G) and q(G) for multidimensional ternary hypercubes. Conversely, they conjectured that, for any G, q(G) is O(s(G)). We present a family {H} of modified multidimensional toruses and conjecture that q(H) is not O(s(H)).en_US
dc.identifier.citationStack and Queue Layouts for Toruses and Extended Hypercubes (with Hussain Heydari, Linda Morales, Hal Sudborough), Proc. Of the Hawaii International Conference on System Sciences, Jan. 2010 (HICSS 10).en_US
dc.identifier.urihttps://hdl.handle.net/10657.1/2329
dc.publisherHawaii International Conference on System Sciencesen_US
dc.subjectHypercubes, Multidimensional systems, Computer science, Upper bound, Lakes, Very large scale integration, Books, Application software, Routing, Parallel processingen_US
dc.titleStack and Queue Layouts for Toruses and Extended Hypercubesen_US
dc.typePresentationen_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Stack and Queue Layouts for Toruses and Extended Hypercubes .pdf
Size:
8.52 KB
Format:
Adobe Portable Document Format
Description:
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

College of Science and Engineering
Said Bettayeb