Algorithms for generating convex sets in acyclic digraphs

ARM Atasu, 2003, Automatic application-specific instruction-set extensions under microarchitectural constraints, 256 Austin, 2002, SimpleScalar: An infrastructure for computer system modeling, Computer, 35, 59, 10.1109/2.982917 Bang-Jensen, 2000 Chen, 2007, Fast identification of custom instructions for extensible processors, IEEE Trans. Computer-Aided Design Integr. Circuits Syst., 26, 359, 10.1109/TCAD.2006.883915 D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, in: Proceedings of the 19th Ann. ACM Symp. on Theory of Computation, 1987, pp. 1–6 Downey, 1999 M.J. Fisher, A.R. Meyer, Boolean matrix multiplication and transitive closure, in: Proceedings of the 12th Ann. ACM Symp. on Switching and Automata Theory, 1971, pp. 129–131 Furman, 1970, Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph, Sov. Math. Dokl., 11, 1252 Gabow, 1978, Finding all spanning trees of directed and undirected graphs, SIAM J. Comput., 7, 280, 10.1137/0207024 G. Gutin, A. Yeo, On the number of connected convex subgraphs of a connected acyclic digraph, Discrete Appl. Math., submitted for publication M.R. Guthaus, J.S. Ringenberg, D. Ernst, T.M. Austin, T. Mudge, R.B. Brown, MiBench: A free, commercially representative embedded benchmark suite, in: Proceedings of the WWC-4, 2001 IEEE International Workshop on Workload Characterization, 2001, pp. 3–14 Kapoor, 1995, Algorithms for enumerating all spanning trees of undirected and weighted graphs, SIAM J. Comput., 24, 247, 10.1137/S009753979225030X Kreher, 1999 Minty, 1965, A simple algorithm for listing all trees of a graph, IEEE Trans. Circuit Theory, CT-12, 120, 10.1109/TCT.1965.1082385 MIPS Pozzi, 2006, Exact and approximate algorithms for the extension of embedded processor instruction sets, IEEE Trans. on CAD of Integrated Circuits and Systems, 25, 1209, 10.1109/TCAD.2005.855950 Read, 1975, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, 5, 237, 10.1002/net.1975.5.3.237 Tensilica The Trimaran Compiler Infrastructure Shioura, 1995, Efficiently scanning all spanning trees of an undirected graph, J. Oper. Res. Soc. Japan, 38, 331 Shioura, 1997, An optimal algorithm for scanning all spanning trees of undirected graphs, SIAM J. Comput., 26, 678, 10.1137/S0097539794270881 T. Uno, A new approach for speeding up enumeration algorithms, in: Proc. ISAAC'98, Lecture Notes Computer Sci., vol. 1533, 1998, pp. 287–296 Yu, 2005, Satisfying real-time constraints with custom instructions, 166