Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-02884025
Contributor : Emmanuel Casseau Connect in order to contact the contributor
Submitted on : Monday, July 27, 2020 - 9:39:47 AM
Last modification on : Saturday, June 25, 2022 - 9:17:28 AM
Long-term archiving on: : Tuesday, December 1, 2020 - 7:12:26 AM

File

TCAS-II_Hal_Inria.pdf
Files produced by the author(s)

Identifiers

Citation

Chenglong Xiao, Shanshan Wang, Wanjun Liu, Xinlin Wang, Emmanuel Casseau. An Optimal Algorithm for Enumerating Connected Convex Subgraphs in Acyclic Digraphs. IEEE Transactions on Circuits and Systems II: Express Briefs, Institute of Electrical and Electronics Engineers, 2021, 68 (1), pp.261-265. ⟨10.1109/TCSII.2020.3000297⟩. ⟨hal-02884025⟩

Share

Metrics

Record views

82

Files downloads

243