On the Consecutive-Retrieval Problem
Ram Swaminathan, Donald K. Wagner · SIAM Journal on Computing · 1994
A $\{ 0,1\} $-matrix M has the consecutive-retrieval property if there exists a tree M such that the vertices of T are indexed on the rows of M and the columns of M are the incidence vectors of the vertex sets of paths of . If such a T exists, then T is a realization for M. In this paper, an $O(r^2 c)$ algorithm is presented to determine whether a given standard, $r \times c$ matrix has the consecutive-retrieval property and, if so, to construct a realization.