An Optimal Algorithm for Enumerating Connected Convex Subgraphs in Acyclic Digraphs

Abstract : Reconfigurable computing system is emerging as an important computing system for satisfying the present and future computing demands in performance and flexibility. Extensible processor is a representative implementation of reconfigurable computing. In this context, custom instruction enumeration problem is one of the most computationally difficult problems involved in custom instruction synthesis for extensible processors. Custom instruction enumeration problem is essentially enumerating connected convex subgraphs from a given application graph. In this paper, we propose a provable optimal algorithm for enumerating connected convex subgraphs in acyclic digraphs in the sense of time complexity. The running time of the proposed algorithm is theoretically proved to be O(C∈CC(G) (|V (C)| + |E(C)|)), where CC(G) denotes the set of connected convex subgraphs in directed acyclic graph G, |V (C)| and |E(C)| denote the number of vertices and the number of edges in subgraph C respectively. Experimental results show that the proposed algorithm is more efficient than the state-of-the-art algorithms in terms of runtime.