The complexity of parallel search (Q1106664)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The complexity of parallel search
scientific article

    Statements

    The complexity of parallel search (English)
    0 references
    0 references
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    deterministic complexity
    0 references
    computational complexity
    0 references
    parallel search
    0 references
    independence systems
    0 references
    matroids
    0 references
    randomized complexity
    0 references
    processor-time trade-offs
    0 references
    0 references
    0 references