Finding the depth of a flow graph

摘要

The depth of a flow graph is the maximum number of back edges in an acyclic path, where a back edge is defined by some depth-first spanning tree for the flow graph. In the case of a reducible graph, the depth is independent of the depth-first spanning tree chosen. We show that the computation of the depth of a reducible flow graph requires polynomial time. Our algorithm is O(ne) on a flow graph of n nodes and e edges. Since e ≤2n for normal flow graphs, our algorithm is really O(n2). While even an O(n2) algorithm is not likely to be acceptable, it is suggestive of the possibility of a more efficient algorithm. Finally, we show that the general problem of computing the depth of an arbitrary flow graph is NP-complete.