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.
['Paul Balister', 'Stefanie Gerke', 'Gregory Gutin', 'Adrian Johnstone', 'Joseph Reddington', 'Elizabeth Scott', 'Arezou Soleimanfallah', 'Anders Yeo']
Algorithms for generating convex sets in acyclic digraphs