**On Competitive On-Line Algorithms for the Dynamic Priority-Ordering Problem**

*G. Ramalingam and Thomas Reps*

University of Wisconsin

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.)