Software configuration management (SCM) systems require the ability to maintain collections of a large number of specific versions of files. One technique for managing these configurations is to maintain a single time-stamp identifying which versions of the files belong to the configuration along with an exception list to that time-stamp. Given the individual time-stamps of n files represented by half-open intervals, we develop an O(n log n) time sequential algorithm that finds a time-stamp leading to the smallest possible exception list. The technique is used in a commercial SCM system and works well in practice. We also develop a parallel version of the algorithm that runs in O(log n) time using n processors on an EREW-PRAM. If the intervals are sorted, the sequential algorithm runs optimally in O(n) time and the parallel algorithm runs optimally in O(log n) time using n= log n processors on an EREW-PRAM.
Citation:
Raymond Greenlaw, Charles Shipley, James Wogulis, "Fast Sequential and Parallel Algorithms for Label Selection to Obtain Space Efficient Implementations in a Software Configuration Management System," parelec, pp.43, International Conference on Parallel Computing in Electrical Engineering (PARELEC'00), 2000