Reduction of Edge Labeled DAGs through Constant Folding

TitleReduction of Edge Labeled DAGs through Constant Folding
Publication TypeReport
Year of Publication2003
AuthorsNaumann, U, Utke, J
Date Published09/2003
Other NumbersANL/MCS-P1073-0803

<p>We present intermediate results for a discrete problem arising in the automatic generation of derivative code. Consider a directed acyclic graph (dag) G = (V,E) with vertex set V = X u Z u Y, where X is the set of minimal vertices, Z is the set of intermediate vertices, Y is the set of maximal vertices, and E is the set of edges (i,j) with i,j in V. X, Y, and Z are pairwise disjoint. The vertices are numbered such that they induce a dependency order, (i,j) in E =&gt; i &lt; j. Each edge (i,j) is annotated with a label c[sub ji] in R. The c[sub ji] can be categorized as either variable or constant. G is transformed into a bipartite graph by using a sequence \\sigma of edge (front and back) and vertex eliminations.</p>