An algorithm for finding connected convex subgraphs of an acyclic digraph

A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. A digraph D is connected if the underlying undirected graph of D is connected. We construct an algorithm for enumeration of all connected convex subgraphs of a connected acyclic digraph D of order n. The time complexity of the algorithm is O(n · cc(D)), where cc(D) is the number of connected convex subgraphs in D. The space complexity is O(n 2). Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology. Our computational experiments demonstrate that our algorithm is better than the state-of-the-art algorithm of Chen, Maskell and Sun. Moreover, unlike the algorithm of Chen, Maskell and Sun, our algorithm has a provable (almost) optimal worst time complexity. Using the same approach, we design an algorithm for generating all connected induced subgraphs of a connected undirected graph G. The complexity of the algorithm is O(n · c(G)), where n is the order of G and c(G) is the number of connected induced subgraphs of G. The previously reported algorithm for connected induced subgraph enumeration is of running time O(mn · c(G)), where m is the number of edges in G.