流图可归约性判定的一个实用算法

A PRACTICAL ALGORITHM FOR REDUCIBILITYDECISION OF FLOW GRAPHS

本文得到了流图Ｇ可归约性判定的一个实用的充要条件．并给出了一个可归约性判定算法，该算法同时计算出Ｇ中各结点的必经结点集．对于不可归约流图，还可指出Ｇ中的所有向后边（ｒｅｔｒｅａｔｉｎｇｅｄｇｅｓ）。对于实际实用，其时间复杂性优于通用的计算必经结点集的算法．

A practical necessary and sufficient condition is obtained for the reducibility decision of flow graph G, and a relevant algorithm which finds the dominators in G at the sam time is given. For the unreducible flow graphs, the algorithm points out all the retreating edges in G.In the applications, its time complexity is better than the popular one which finds dominators only.