Parallelism in Randomized Incremental Algorithms

2016/07/08 by Guy E. Blelloch, Yan Gu, Julian Shun +1 · 1 citation
Computer Science · Mathematics · #Algorithm #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Data Management and Algorithms #Delaunay triangulation #Mathematics #Parallel algorithm #Parallel computing #Parallelism (grammar) #Randomized algorithm #Sorting #Sorting algorithm #Theoretical computer science #Triangulation

paper · pdf · doi:10.1145/2935764.2935766

openalex publication_date 2016/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

In this paper we show that most sequential randomized incremental algorithms are in fact parallel. We consider several random incremental algorithms including algorithms for comparison sorting and Delaunay triangulation; linear programming, closest pair, and smallest enclosing disk in constant dimensions; as well as least-element lists and strongly connected components on graphs.

Citations

• Parallel Correlation Clustering on Big Graphs
• Parallel Merge Sort
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Depth-first search is inherently sequential
• Depth-First Search and Linear Graph Algorithms
• On fast parallel detection of strongly connected components (SCC) in small-world graphs

Cited by

• Strongly connected component [wikipedia]

Related

• Parallelism in Randomized Incremental Algorithms
• Greedy Sequential Maximal Independent Set and Matching are Parallel on Average
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets
• Using parallelism techniques to improve sequential and multi-core sorting performance
• A Parallel Algorithm for Generating a Random Graph with a Prescribed Degree Sequence