## Reduction of Edge Labeled DAGs through Constant Folding

Title | Reduction of Edge Labeled DAGs through Constant Folding |

Publication Type | Report |

Year of Publication | 2003 |

Authors | Naumann, U, Utke, J |

Date Published | 09/2003 |

Other Numbers | ANL/MCS-P1073-0803 |

Abstract | <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 => i < 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> |

http://www.mcs.anl.gov/papers/P1073.pdf |