Queue Layouts and Staircase Covers of Matrices

Simple item page
dc.contributor.authorAbrams, Marcen
dc.contributor.authorBatongbacal, Alanen
dc.contributor.authorRibler, Randyen
dc.contributor.authorVazirani, Devendraen
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorPemmaraju, Sriram V.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:37:15Zen
dc.date.available2013-06-19T14:37:15Zen
dc.date.issued1994-06-01en
dc.description.abstractA connection between a queue layout of an undirected graph and a staircase cover of its adjacency matrix is established. The connection is exploited to establish a number of combinatorial results relating the number of vertices, the number of edges, and the queue number of a queue layout. The staircase notion is generalized to that of an (h,w)- staircase, and an efficient algorithm to optimally cover a matrix with (h,w)- staircases is presented. The algorithm is applied to problems of monotonic subsequences and to the maxdominance problem of Atallah and Kosaraju.en
dc.format.mimetypeapplication/postscripten
dc.identifierhttp://eprints.cs.vt.edu/archive/00000404/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000404/01/TR-94-22.psen
dc.identifier.trnumberTR-94-22en
dc.identifier.urihttp://hdl.handle.net/10919/19883en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleQueue Layouts and Staircase Covers of Matricesen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Name:
TR-94-22.ps
Size:
271.89 KB
Format:
Postscript Files
Download

Collections

Computer Science Technical Reports