Algorithms for generating convex sets in acyclic digraphs
A set X of vertices of an acyclic digraph D  is convex if X?? 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?? 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 A for enumeration of all connected convex sets of an acyclic digraph D of order n . The time complexity of A A is O(n?cc(D)) O ( n ? cc ( D ) ) , where cc(D) 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.
convex sets acyclic digraphs embedded processors enumeration algorithms