A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem
Paul F. Dietz, Merrick L. Furst, John E. Hopcroft · eCommons (Cornell University) · 1979
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for efficient retrieval. A linear time algorithm for the GCRP is given. Further generalization leads to problems that are complete for NP.