S-t connectivity is a decision problem asking, for vertices s and t in a graph, if t is reachable from s. Many parallel solutions for GPUs have been proposed in literature to solve the problem. The most efficient, which rely on two concurrent BFS starting from s and t have shown limitations when applied on sparse graphs (i.e., graphs with low average degree). In this paper we present FAST-CON, an alternative solution based on multi- source BFS and adjacency matrix to better exploit the massive parallelism of the GPU architectures with any type of graph. The results show that FAST-CON achieves speedup up to one order of magnitude for dense graphs and up to two orders of magnitude for sparse graph compared to the state of the art solutions.
File in questo prodotto:
Non ci sono file associati a questo prodotto.