Journal article
Stack and Queue Layouts of Posets
SIAM journal on discrete mathematics, Vol.10(4), pp.599-625
11/1997
DOI: 10.1137/S0895480193252380
Abstract
The stacknumber (queuenumber) of a poset is defined as the stacknumber (queuenumber) of its Hasse diagram viewed as a directed acyclic graph. Upper bounds on the queuenumber of a poset are derived in terms of its jumpnumber, its length, its width, and the queuenumber of its covering graph. A lower bound of Ω(√n) is shown for the queuenumber of the class of n-element planar posets. The queuenumber of a planar poset is shown to be within a small constant factor of its width. The stacknumber of n-element posets with planar covering graphs is shown to be Θ(n). These results exhibit sharp differences between the stacknumber and queuenumber of posets as well as between the stacknumber (queuenumber) of a poset and the stacknumber (queuenumber) of its covering graph.
Details
- Title: Subtitle
- Stack and Queue Layouts of Posets
- Creators
- Lenwood S. HeathSriram V. Pemmaraju
- Resource Type
- Journal article
- Publication Details
- SIAM journal on discrete mathematics, Vol.10(4), pp.599-625
- DOI
- 10.1137/S0895480193252380
- ISSN
- 0895-4801
- eISSN
- 1095-7146
- Language
- English
- Date published
- 11/1997
- Academic Unit
- Computer Science
- Record Identifier
- 9984259406102771
Metrics
24 Record Views