Stack and Queue Layouts of Posets
| dc.contributor.author | Heath, Lenwood S. | en |
| dc.contributor.author | Pemmaraju, Sriram V. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:35:43Z | en |
| dc.date.available | 2013-06-19T14:35:43Z | en |
| dc.date.issued | 1992 | en |
| dc.description.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 is shown for the queuenumber of the class of planar posets. The queuenumber of a planar poset is shown to be within a small constant factor of its width. The stacknumber of posets with planar covering graphs is shown to be . 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. | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000311/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000311/01/TR-92-31.pdf | en |
| dc.identifier.trnumber | TR-92-31 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19732 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Stack and Queue Layouts of Posets | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1