The complexity of parallel search (Q1106664)

The subject of the paper is the computational complexity of some parallel search algorithms within the framework of independence systems. Evolved from earlier work on parallel algorithms for concrete problems (the determination of a maximal independent set of vertices or a maximum matching in a graph), the research results in a parallel analog of the self-reducibility process, specific for sequential computation. Three types of independence systems are considered: matroids, graphic matroids and partition matroids. Lower and upper bounds on the deterministic and randomized complexity of these problems are derived. These bounds may be used to highlight the processor-time trade-offs that are possible. In the same time, it results that randomized parallel algorithms are much more powerful than deterministic ones, and even the randomized algorithms cannot make effective use of extremely large numbers of processors.