On competitive on-line algorithms for the dynamic priority-ordering problem

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