This paper introduces the first gpu-based parallel algorithms to solve the fastest path duration (fpd) problem in temporal graphs. Fastest path duration in temporal graphs is a well studied problem that has multiple use cases in information diffusion, epidemic spreading, and route planning in public transportation. Given a temporal graph G in which each edge associates with a departure time and duration time, and a source vertex s, the Fastest Path Duration (fpd) problem is to compute the journey times from s to all the rest of the vertices in G. The existing multi-core algorithm for fpd by Delling et al. exhibits limited parallelism. In general, many parallel algorithms suffer from doing redundant work while pruning certain computations. Our research focuses on multiple algorithmic ways to avoid redundant work and perform pruning of computations effectively. We introduce three novel gpu-based parallel algorithms for fpd, namely Level Order (lo), Multiple Breadth First Search (mbfs), and Local Work-lists (lw) and implement them on a gpu architecture machine. Our algorithms demonstrate an average speedup of approximately 165 times and a maximum speedup of up to 1383 times over the current state-of-the-art algorithms. This paper provides a comprehensive explanation of various algorithm designs, their optimizations for gpus, and an extensive evaluation of their performance across various temporal graph scenarios.

Finding the biconnected components of a graph has a large number of applications in many other graph problems including planarity testing, computing the centrality metrics, finding the (weighted) vertex cover, coloring, and the like. Recent years saw the design of efficient algorithms for this problem across sequential and parallel computational models. However, current algorithms do not work in the setting where the underlying graph changes over time in a dynamic manner via the insertion or deletion of edges. Dynamic algorithms in the sequential setting that obtain the biconnected components of a graph upon insertion or deletion of a single edge are known from over two decades ago. Parallel algorithms for this problem are not heavily studied. In this paper, we design shared-memory parallel algorithms that obtain the biconnected components of a graph subsequent to the insertion or deletion of a batch of edges. Our algorithms hence will be capable of exploiting the parallelism adduced due to a batch of updates. We implement our algorithms on an AMD EPYC 7742 CPU having 128 cores. Our experiments on a collection of 10 real-world graphs from multiple classes indicate that our algorithms outperform parallel state-of-the-art static algorithms.11The implementation and an extended version of this paper is at [5].

Given a temporal graph G, a source vertex s, and a departure time at source vertex ts, the earliest arrival time problem (EAT) is to start from s on or after tsand reach all the vertices in G as early as possible. Ni et al. have proposed a parallel algorithm for EAT and obtained a speedup up to 9.5× on real-world graphs with respect to the connection-scan serial algorithm by using multi-core processors. We propose a topology-driven parallel algorithm for EAT on public transport networks and implement using general-purpose programming on the graphics processing unit (GPU). A temporal connection in a temporal graph for a public transport network is associated with a departure time and a duration time, and many connections exist from u to v for an edge ( u, v). We propose two pruning techniques connection-type and clustering, and use arithmetic progression technique appropriately to process many connections of an edge, without scanning all of them. In the connection-type technique, the connections of an edge with the same duration are grouped together. In the clustering technique, we follow 24-hour format and the connections of an edge are partitioned into 24 clusters so that the departure time of connections in the ithcluster is at least i-hour and at most i+1-hour. The arithmetic progression technique helps to store a sequence of departure times of various connections in a compact way. We propose a hybrid approach to combine the three techniques (connection-type, clustering and arithmetic progression) in an efficient way. Our techniques achieve an average speedup up to 61× when compared to the existing connection-scan serial algorithm running on CPU. Also, the average speedup of our algorithm is 12.65× against the parallel edge-scan-dependency graph algorithm running on GPU.