References Cited

DIM06

9th DIMACS implementation challenge - Shortest paths. \tt http://www.dis.uniroma1.it/challenge9/, 2006.

ANTT02

Arvind Arasu, Jasmine Novak, Andrew Tomkins, and John Tomlin. PageRank computation and the structure of the web: Experiments and algorithms. In WWW, 107–117. 2002.

AAB+20

Ariful Azad, Mohsen Mahmoudi Aznaveh, Scott Beamer, Mark Blanco, Jinhao Chen, Luke D'Alessandro, Roshan Dathathri, Tim Davis, Kevin Deweese, Jesun Firoz, and others. Evaluation of graph analytics frameworks using the gap benchmark suite. In 2020 IEEE International Symposium on Workload Characterization (IISWC), 216–227. IEEE, 2020.

BAsanovicP15

Scott Beamer, Krste Asanović, and David Patterson. The GAP Benchmark Suite. arXiv preprint arXiv:1508.03919, 2015.

BAsanovicP12

Scott Beamer, Krste Asanović, and David A. Patterson. Direction-optimizing breadth-first search. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2012.

BV04

Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: compression techniques. WWW, pages 595–601, 2004.

BK01

Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. In Proceedings of the Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR '01, 359–374. Berlin, Heidelberg, 2001. Springer-Verlag.

Bra01

Ulrik Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163–177, 2001. URL: https://doi.org/10.1080/0022250X.2001.9990249, doi:10.1080/0022250X.2001.9990249.

DezsHoJuttnerKovacs11

Balázs Dezső, Alpár Jüttner, and Péter Kovács. Lemon–an open source c++ graph template library. Electronic Notes in Theoretical Computer Science, 264(5):23–45, 2011.

ErdHosRenyi59

Paul Erdős and Alfréd Rényi. On random graphs. I. Publicationes Mathematicae, 6:290–297, 1959.

GL05

Douglas Gregor and Andrew Lumsdaine. Lifting sequential graph algorithms for distributed-memory parallel computation. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '05, 423–437. New York, NY, USA, 2005. Association for Computing Machinery. URL: https://doi.org/10.1145/1094811.1094844, doi:10.1145/1094811.1094844.

JP93

Mark T Jones and Paul E Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 14(3):654–669, 1993.

KPW+07

Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and L. Paul Chew. Optimistic parallelism requires abstractions. In PLDI, 211–222. ACM, 2007. URL: https://doi.org/10.1145/1250734.1250759, doi:10.1145/1250734.1250759.

KLPM10

Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is Twitter, a social network or a news media? WWW, 2010.

MS03

Ulrich Meyer and Peter Sanders. Δ-stepping: a parallelizable shortest path algorithm. Journal of Algorithms, 49(1):114 – 152, 2003. 1998 European Symposium on Algorithms. URL: http://www.sciencedirect.com/science/article/pii/ S0196677403000762, doi:https://doi.org/10.1016/S0196-6774(03)00076-2.

MWBA10

Richard C. Murphy, Kyle B. Wheeler, Brian W Barrett, and James A. Ang. Introducing the Graph 500. In Cray User's Group. CUG, 2010.

MS89

David R. Musser and Alexander A. Stepanov. Generic programming. In P Gianni, editor, International Symposium ISSAC 1988, volume 38 of Lecture Notes in Computer Science, pages 13–25. Springer-Verlag, 1989.

NCDB18

Eric Niebler, Casey Carter, and Christopher Di Bella. The one ranges proposal. Technical Report, Tech. rep. P0896r4. Nov. 2018. url: http://www. open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r4. pdf, 2018.

Orz04

S. M. Orzan. On Distributed Verification and Verified Distribution. Ph.D. thesis, VRIJE UNIVERSITEIT, November 2004. URL: http://dare.ubvu.vu.nl/handle/1871/10338.

SML15

Roman Shaposhnik, Claudio Martella, and Dionysios Logothetis. Practical Graph Analytics with Apache Giraph. Apress, New York, 1st ed. edition edition, October 2015. ISBN 978-1-4842-1252-3.

SV80

Yossi Shiloach and Uzi Vishkin. An O(log n) parallel connectivity algorithm. Technical Report, Computer Science Department, Technion, 1980.

SDB14

J. Shun, L. Dhulipala, and G. Blelloch. A simple and practical linear-work parallel algorithm for connectivity. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, 143–153. ACM, 2014. URL: http://doi.acm.org/10.1145/2612669.2612692, doi:10.1145/2612669.2612692.

SB13

Julian Shun and Guy E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, 135–146. New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2442516.2442530, doi:10.1145/2442516.2442530.

SLL02

Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 2002.

SL95

Alexander Stepanov and Meng Lee. The standard template library. Technical Report HPL-95-11, HP Laboratories, November 1995.

SR14

Alexander A Stepanov and Daniel E Rose. From mathematics to generic programming. Pearson Education, 2014.

SBNB18

Michael Sutton, Tal Ben-Nun, and Amnon Barak. Optimizing parallel graph connectivity computation via subgraph sampling. In IPDPS, 12–21. IEEE, 2018.

WDP+16

Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens. Gunrock: A high-performance graph processing library on the GPU. In PPoPP. 2016.

YCX+14

Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, and Yingyi Bu. Pregel algorithms for graph connectivity problems with performance guarantees. Proc. VLDB Endow., 7(14):1821–1832, 2014. URL: http://dx.doi.org/10.14778/2733085.2733089, doi:10.14778/2733085.2733089.

ZBC+20

Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun. Optimizing ordered graph algorithms with GraphIt. In CGO, 158–170. ACM, 2020. URL: https://doi.org/10.1145/3368826.3377909, doi:10.1145/3368826.3377909.

ZYB+18

Yunming Zhang, Mengjiao Yang, Riyadh Baghdadi, Shoaib Kamil, Julian Shun, and Saman Amarasinghe. GraphIt: A high-performance graph DSL. PACMPL/OOPSLA, 2:121:1–121:30, October 2018.

Intel20

Intel. Intel Threading Building Blocks (TBB). 2020. URL: https://github.com/oneapi-src/oneTBB.

LumsdaineDalessandroDeweese+20

Andrew Lumsdaine, Luke Dalessandro, Kevin Deweese, Jesun Firoz, and Scott McMillan. Triangle counting with cyclic distributions. In 2020 IEEE High Performance Extreme Computing Conference (HPEC), volume, 1–8. 2020. doi:10.1109/HPEC43674.2020.9286220.