Search

Circuits in a graph are interesting structures and identifying them is of an important relevance for many applications. However, enumerating circuits is known to be a difficult problem, since their number can grow exponentially. In this paper, we propose fast parallel approaches for enumerating elementary circuits of directed graphs based on graphics processing unit (GPU). Our algorithms are based on a massive exploration of the graph in a breadth-first search strategy. Algorithm V-FEC explores the graph starting from different vertices simultaneously. To further reduce the search space, we present T-FEC, another algorithm that uses triplets as an initial set to start exploring. To the best of our knowledge, those are the first parallel GPU-based algorithms for finding all circuits of a given graph. In addition, they find circuits of a given length and circuits with a specific vertex or edge. The evaluation results show that the proposed approaches achieve up to 190x speed-up over Johnson's algorithm, one of the most efficient sequential algorithms for finding circuits. [ABSTRACT FROM AUTHOR]

Abstract: An arc going out from a vertex x in a digraph is called an out-arc of x. Yao et al. [Discrete Appl. Math. 99 (2000) 245–249] proved that every strong tournament contains a vertex x such that all out-arcs of x are pancyclic. Recently, Yeo [J. Graph Theory 50 (2005) 212–219] proved that each 3-strong tournament contains two such vertices. In this paper, we confirm that Yeo''s result is also true for 2-strong tournaments. Our proof implies a polynomial algorithm to find two such vertices. [Copyright &y& Elsevier]