Computing Breadth First Search in Large Graph Using hMetis Partitioning

Free registration required

Executive Summary

In this paper, the authors present a new algorithm for the Breadth First Search traversing based on hMetis partitioning. hMetis is a hyper graph partitioning algorithm that divides the massive graph into sub-graphs. Their heuristic approach of computing the Breadth First Search (h-BFS) starts at the partition that contains the source node then processing the other fragments piece by piece based on the border edges. Experimental results show that proposed algorithm is simpler and faster of traversing the large graph that does not fit in the memory based on the time and the number of I/O operations.

  • Format: PDF
  • Size: 270.33 KB