Queue Layouts and Staircase Covers of Matrices
| dc.contributor.author | Abrams, Marc | en |
| dc.contributor.author | Batongbacal, Alan | en |
| dc.contributor.author | Ribler, Randy | en |
| dc.contributor.author | Vazirani, Devendra | en |
| 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:37:15Z | en |
| dc.date.available | 2013-06-19T14:37:15Z | en |
| dc.date.issued | 1994-06-01 | en |
| dc.description.abstract | A 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.mimetype | application/postscript | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000404/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000404/01/TR-94-22.ps | en |
| dc.identifier.trnumber | TR-94-22 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19883 | 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 | Queue Layouts and Staircase Covers of Matrices | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1