ABSTRACT
Maximal independent set and maximal matching are fundamental problems studied in computer science. In the sequential case, a greedy linear time algorithm can be used to solve these problems. However, in parallel computation these problems are not trivial. Currently fastest parallel algorithms for these problems are obtained through derandomization [7-9,11]. Owing to the complications of the application of derandomization technique, the parallel algorithms obtained [9] were not well understood. We will explain the details of the derandomization technique and its applications to the maximal independent set and maximal matching problem in this chapter. Instead of using an O(2n) sized sample space for the bit pairs PROFIT/COST problem as was done in Reference 9, we follow Luby’s algorithm [18,19], and use an O(n) sized sample space. This simplifies the approach presented in Reference 9.
