An algorithm for finding input–output constrained convex sets in an acyclic digraph

A set X of vertices of an acyclic graph is convex if any vertex on a directed walk between elements of X is itself in X. We construct an algorithm for generating all input–output constrained convex (IOCC) sets in an acyclic digraph, which uses several novel ideas. We show that the time complexity of our algorithm significantly improves the best one known from the literature. IOCC sets of acyclic digraphs are of interest in the area of modern embedded processor technology.