Breadth first search on massive graphs

Files in This Item:
File Description SizeFormat 
ajwani_bfs-book-chapter.pdf169.06 kBAdobe PDFDownload
Title: Breadth first search on massive graphs
Authors: Ajwani, DeepakDementiev, RomanMeyer, UlrichOsipov, 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 [29] and later Mehlhorn and Meyer [27] 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. [3] 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 strategyAlgorithmsRAM 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

Page view(s)

139
Last Week
7
Last month
checked on Nov 22, 2019

Download(s)

47
checked on Nov 22, 2019

Google ScholarTM

Check

Altmetric


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.