Graph Connectivity in Log Steps Using Label Propagation

DOI10.1142/S0129626421500213zbMath1490.68295arXiv1808.06705OpenAlexW4206190346MaRDI QIDQ5087066

Paul Burkhardt

Publication date: 8 July 2022

Published in: Parallel Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.06705

zbMATH Keywords

connected componentsparallel algorithmgraph connectivityPRAMMapReduce

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Uses Software

• MapReduce
• SNAP
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Selection and sorting with limited storage
• A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
• Sorting, Searching, and Simulation in the MapReduce Framework
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• An O(logn) parallel connectivity algorithm
• Fast Connected Components Algorithms for the EREW PRAM
• A Simpler Parallel Algorithm for Graph Connectivity
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Communication Steps for Parallel Query Processing
• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• Parallelism in random access machines
• Sequential Operations in Digital Picture Processing
• Trading off space for passes in graph streaming problems

This page was built for publication: Graph Connectivity in Log Steps Using Label Propagation