Abrams, MarcBatongbacal, AlanRibler, RandyVazirani, DevendraHeath, Lenwood S.Pemmaraju, Sriram V.2013-06-192013-06-191994-06-01http://hdl.handle.net/10919/19883A 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.application/postscriptenIn CopyrightTechnical reportTR-94-22http://eprints.cs.vt.edu/archive/00000404/01/TR-94-22.ps