A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem
Collections
Author
Dietz, Paul F.
Furst, Merrick
Hopcroft, John E.
Abstract
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.
Date Issued
1979-07
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR79-386
Type
technical report