Breadth first search on massive graphs
Files in This Item:
|ajwani_bfs-book-chapter.pdf||169.06 kB||Adobe PDF||Download|
|Title:||Breadth first search on massive graphs||Authors:||Ajwani, Deepak; Dementiev, Roman; Meyer, Ulrich; Osipov, Vitaly||Permanent link:||http://hdl.handle.net/10197/10869||Date:||2009||Online since:||2019-07-10T10:15:42Z||Abstract:||We consider the problem of Breadth First Search (BFS) traversal on massive sparse undirected graphs. Despite the existence of simple linear time algorithms in the RAM model, it was considered non-viable for massive graphs because of the I/O cost it incurs. Munagala and Ranade  and later Mehlhorn and Meyer  gave efficient algorithms (refered to as MR BFS and MM BFS, respectively) for computing BFS level decompositions in an external memory model. Ajwani et al.  implemented MR BFS and the randomized variant of MM BFS using the external memory library STXXL and gave a comparative study of the two algorithms on various graph classes. In this paper, we review and extend that result demonstrating the effectiveness and viability of the BFS implementations on various other synthetic and real world benchmarks. Furthermore, we present the implementation of the deterministic variant of MM BFS and show that in most cases, it outperforms the randomized variant.||metadata.dc.description.othersponsorship:||DFG - German Research Grant||Type of material:||Conference Publication||Publisher:||American Mathematical Society||Keywords:||Breadth First Search (BFS); Graph traversal strategy; Algorithms; RAM model||Other versions:||http://users.diag.uniroma1.it/challenge9/||Language:||en||Status of Item:||Not peer reviewed||Is part of:||Demetrescu, C., Goldberg, A. V., Johnson, D. S. (eds.). The Shortest Path Problem: Ninth DIMACS Implementation Challenge||Conference Details:||9th Implementation Challenge of DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway, NJ, 22 March 2006||ISBN:||978-0-8218-4383-3|
|Appears in Collections:||Computer Science Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.