Breadth first search on massive graphs

DC FieldValueLanguage
dc.contributor.authorAjwani, Deepak-
dc.contributor.authorDementiev, Roman-
dc.contributor.authorMeyer, Ulrich-
dc.contributor.authorOsipov, Vitaly-
dc.date.accessioned2019-07-10T10:15:42Z-
dc.date.available2019-07-10T10:15:42Z-
dc.date.issued2009-
dc.identifier.isbn978-0-8218-4383-3-
dc.identifier.issn1052-1798-
dc.identifier.urihttp://hdl.handle.net/10197/10869-
dc.description9th Implementation Challenge of DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway, NJ, 22 March 2006en_US
dc.description.abstractWe 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.en_US
dc.language.isoenen_US
dc.publisherAmerican Mathematical Societyen_US
dc.relation.ispartofDemetrescu, C., Goldberg, A. V., Johnson, D. S. (eds.). The Shortest Path Problem: Ninth DIMACS Implementation Challengeen_US
dc.subjectBreadth First Search (BFS)en_US
dc.subjectGraph traversal strategyen_US
dc.subjectAlgorithmsen_US
dc.subjectRAM modelen_US
dc.titleBreadth first search on massive graphsen_US
dc.typeConference Publicationen_US
dc.internal.authorcontactotherdeepak.ajwani@ucd.ieen_US
dc.internal.webversionshttp://users.diag.uniroma1.it/challenge9/-
dc.statusNot peer revieweden_US
dc.neeo.contributorAjwani|Deepak|aut|-
dc.neeo.contributorDementiev|Roman|aut|-
dc.neeo.contributorMeyer|Ulrich|aut|-
dc.neeo.contributorOsipov|Vitaly|aut|-
dc.description.othersponsorshipDFG - German Research Granten_US
dc.date.updated2019-04-01T10:33:53Z-
dc.identifier.grantidDFG - SA 933/1-3-
dc.identifier.grantidDFG - ME 2088/1-3-
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:Computer Science Research Collection
Files in This Item:
File Description SizeFormat 
ajwani_bfs-book-chapter.pdf169.06 kBAdobe PDFDownload
Show simple item record

Page view(s)

156
Last Week
5
Last month
checked on Dec 15, 2019

Download(s)

55
checked on Dec 15, 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.