Considering myself a researcher in graph algorithms, I’ve come to the surprising realization that my grasp of these algorithms is not as solid as I thought. Hence, this blog series aims to document my exploration of various graph algorithms I’ve encountered thus far, regardless of their complexity.
The algorithms are selected from the parallel graph frameworks GAP and GBBS, focusing on their single-threaded versions to assess their complexity.
- Breadth-First Search (BFS)
- Single-Source Shortest Paths (SSSP)
- Connected Components (CC)
- Betweenness Centrality (BC)
- Triangle Counting (TC)
- Minimum Spanning Tree (MST)
- Strongly Connected Components (SCC)
- SCAN Clustering (SCAN)
- Low Diameter Decomposition (LDD)
- Biconnected-Components (BC)
- Graph Coloring (COLOR)
- Maximal Matching (MM)
- Maximal Independent Set (MIS)