Algorithms for generating convex sets in acyclic digraphs

A set X of vertices of an acyclic digraph D is convex if X≠∅ and there is no directed path between vertices of X which contains a vertex not in X. A set X is connected if X≠∅ and the underlying undirected graph of the subgraph of D induced by X is connected. Connected convex sets and convex sets of acyclic digraphs are of interest in the area of modern embedded processor technology. We construct an algorithm A for enumeration of all connected convex sets of an acyclic digraph D of order n. The time complexity of A is O(n⋅cc(D)), where cc(D) is the number of connected convex sets in D. We also give an optimal algorithm for enumeration of all (not just connected) convex sets of an acyclic digraph D of order n. In computational experiments we demonstrate that our algorithms outperform the best algorithms in the literature.