Multi-core Spanning Forest Algorithms using the Disjoint-set Data Structure
2012pp. 827–835
Citations Over TimeTop 10% of 2012 papers
Abstract
We present new multi-core algorithms for computing spanning forests and connected components of large sparse graphs. The algorithms are based on the use of the disjoint-set data structure. When compared with the previous best algorithms for these problems our algorithms are appealing for several reasons: Extensive experiments using up to 40 threads on several different types of graphs show that they scale better. Also, the new algorithms do not make use of any hardware specific routines, and thus are highly portable. Finally, the algorithms are quite simple and easy to implement.
Related Papers
- → Disjoint skolem sequences and related disjoint structures(1993)8 cited
- → New Characterizations of Simple Points, Minimal Non-simple Sets and P-Simple Points in 2D, 3D and 4D Discrete Spaces(2008)6 cited
- → Separating H-sets by Open Sets(2010)
- Parallel Computation of Disjoint Products Approach(2002)
- → MAXIMUM DISJOINT SET(2018)