A one-way array algorithm for matroid scheduling
Matthias F. M. Stallmann · 1991
The greedy algorithm is a standard paradigm for solving matroid optimization problems on sequential computers. This paper presents a greedy algorithm suitable for a fully-pipelined linear array of processors, a generalization of Huang's algorithm [Hua90] for minimum spanning trees. Application of the algorithm to uniprocessor scheduling with release times and deadlines is discussed in detail. A key feature of the algorithm is its use of matroid contraction.