Overview
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- Breadth-First Search
- Integral-Weight SSSP
- Positive-Weight SSSP
- General-Weight SSSP
- Single-Source Widest Path
- Single-Source Betwenness Centrality
- Graph Spanner
#
Connectivity Problems- Low-Diameter Decomposition
- Connectivity
- Biconnectivity
- Strongly Connected Components
- Minimum Spanning Forest
#
Covering Problems#
Substructure Problems- Triangle Counting
- -Clique Counting
- -Core
- -Truss
- Approximate Densest Subgraph
- Low-Outdegree Orientation (Arboricity Ordering)