Skip to main content


This page specifies the graph problems considered in GBBS. Accessing one of the benchmark pages below provides the following information:

  • Formal input-output specification of the problem.
  • Algorithms solving the problem. Specifically, for each algorithm we provide:
    • Pointers to the code on github implementing the algorithm
    • Work and depth bounds of the algorithm
    • References to the papers/sources for the algorithm
  • Examples of how to compile and run an implementation on a graph input.

We note that we are continuing to work on new benchmarks, and new implementations of existing problems, and so the data here may only be partially complete (please check our github repo for the latest state).

Shortest Path Problems#

Connectivity Problems#

Covering Problems#

Substructure Problems#

Eigenvector Problems#