Fast sequential and parallel algorithms for label selection to obtain space efficient implementations in a software configuration management system

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) tone 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