Point-to-point shortest path (PPSP), or s-t connectivity, is a variant of the shortest path problem found in graph theory. In this problem, we are given a graph and pairs of vertices over time, and the output is the shortest path between each pair of …
Effective scheduling and load balancing of applications on massively multi-threading systems remains challenging despite decades of research, especially for irregular and data dependent problems where the execution control path is unknown until …
The k-core of a graph is a metric used in a wide range of applications, including social networks analytics, visualization, and graph coloring. Finding the maximal k-core of a graph can be be done in near linear time. The low computational …
Triangle counting is a building block for numerous graph applications and given the fact that graphs continue to grow in size, its scalability is important. As such, numerous algorithms have been designed for triangle counting-some of which are …
The Betweenness Centrality of a vertex is an important metric used for determining how “central” a vertex is in a graph based on the number of shortest paths going through that vertex. Computing the betweenness centrality of a graph is …