Graph algorithms such as BFS and SSSP (Bellman-Ford or Dijkstra's algorithm) generally exhibit a lack of locality. A vertex at the start of the graph may want to update an edge that exists in a farther part of the graph. This is a problem in graphs whose memory requirements far exceed those available in the machine's DRAM. How must the graph be streamed into the machine in this case? What are the consequences for a parallel multicore in such cases where access latency and core utilization are of utmost importance?
You could combine clusters of vertices to super-vertices, find a route through them and delete all vertices of the original graph whose vertices are not contained in a visited super-vertex. Then you proceed with a smaller graph and smaller super-vertices.
Regards,
Joachim
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms