The diameter of a graph is a fundamental topological parameter that provides valuable insight needed in multiple areas of graph analytics. The traditional approach to computing the diameter is solving the all-pairs shortest-paths problem (APSP). Since APSP has a time complexity that is at least quadratic in the size of the graph, it is impractical for large graphs. As a remedy, leading algorithms use Breadth-First Search (BFS) combined with various optimizations to limit the number of BFS calls required to find the diameter. We present a new algorithm called F-Diam for quickly computing the exact diameter of large graphs. It includes new techniques such as Winnowing to greatly reduce the number of BFS calls. Our parallel CPU implementation of F-Diam is faster than the state of the art on all tested inputs, often by orders of magnitude.

Subgraph Counting (SGC) is a fundamental component of many important applications, including cybersecurity, drug discovery, social network analysis, and natural language processing. However, current SGC approaches can only handle very small patterns (aka subgraphs) because the computational load increases exponentially with the size of the pattern. To overcome this limitation for certain patterns, we introduce a new technique and algorithm called Fringe-SGC for counting the exact number of times a subgraph occurs in a larger graph. Our approach conventionally searches only for the “core” of the subgraph and then uses set-based methods to compute the number of occurrences that the “fringes” add. Our evaluation shows that Fringe-SGC is able to count the instances of many subgraphs that are too large for state-of-the-art SGC frameworks. Furthermore, Fringe-SGC running on a GPU outperforms the state-of-the-art GPU-based SGC frameworks by up to 20 × on average, especially on patterns with many fringes.