A Graph Parsing Algorithm and Implementation
Carolyn L. McCreary, Alan Reed · 1993
This paper presents an algorithm for decomposing directed acyclic graphs (DAGs) into a heirarchy of subgraphs we call clans. The resulting parse tree is being used to partition and schedule program dependence graphs for efficient concurrent execution on a parallel system. The clans can be identified as able or unable to support parallel execution, and their connections with other clans is completely characterized in the parse tree. . 2 Definitions and Concepts