The vertices of a directed acyclic graph (DAG) are said to be correctly prioritized if every vertex v in the graph is assigned a priority, denoted by priority(v), such that if there is an edge in the DAG from vertex v to vertex w then priority(v) < priority(w). The dynamic priority-ordering problem is to maintain a correct prioritization of the graph as the DAG is modified. Alpern et al. presented an algorithm for this problem. In this paper we show that the Alpern et al. algorithm does not have a constant competitive ratio, where the cost of the algorithm is measured in terms of the number of primitive priority-manipulation operations. The proof also shows that there exists no algorithm for the problem that has a constant competitive ratio, as long as the allowed primitive priority-manipulation operations satisfy a simple property. The proof that we give also shows that there exists no algorithm for the problem of maintaining a topological-sort ordering that has a constant competitive ratio.

Keywords: Analysis of algorithms, competitive ratio, dynamic priority-ordering problem, dynamic topological-sorting problem

(Click here to access the paper: PostScript, PDF.)