Computing Frequency Dominators and Related Problems

摘要

We consider the problem of finding frequency dominators in a directed graph with a single source vertex and a single terminal vertex. A vertex x is a frequency dominator of a vertex y if and only if in each source to terminal path, the number of occurrences of x is at least equal to the number of occurrences of y. This problem was introduced in a paper by Lee et al. [11] in the context of dynamic program optimization, where an efficient algorithm to compute the frequency dominance relation in reducible graphs was given. In this paper we show that frequency dominators can be efficiently computed in general directed graphs. Specifically, we present an algorithm that computes a sparse (O(n)-space), implicit representation of the frequency dominance relation in O(m + n) time, where n is the number of vertices and m is the number of arcs of the input graph. Given this representation we can report all the frequency dominators of a vertex in time proportional to the output size, and answer queries of whether a vertex x is a frequency dominator of a vertex y in constant time. Therefore, we get the same asymptotic complexity as for the regular dominators problem. We also show that, given our representation of frequency dominance, we can partition the vertex set into regions in O(n) time, such that all vertices in the same region have equal number of appearances in any source to terminal path. The computation of regions has applications in program optimization and parallelization.