In an undirected graph, a connected component is a subgraph in which any two vertices are connected to each other by paths. Usual algorithms build a graph where each vertex is labeled with its component number. They use a search from an unclassified vertex to build the connected component containing…
The BSP Model The Bulk Synchronous Parallel (BSP) is a model for designing parallel algorithms. The BSP model was developed by Leslie Valiant of Harvard University during the 1980s and published in 1990. Computation proceeds as a sequence of iterations, called supersteps. Each superstep involves a phase of parallel computations,…
Pour mener des expérimentations sur de très grands graphes (plusieurs centaines de millions d’éléments), les chercheurs doivent se tourner vers des infrastructures distribuées. Les middlewares existants de calculs distribués sur les graphes affichent certaines limites quand à leurs modèles et leurs performances. À partir de l’étude de ces middlewares, l’ADT…
