ONLINE ALGORITHMS FOR ORDERED SETS AND COMPARABILITY-GRAPHS

We discuss several results concerning on-line algorithms for ordered s ets and comparability graphs. The main new result is on the problem of on-line transitive orientation. We view on-line transitive orientatio n of a comparability graph G as a two-person game. In the ith round of play, 1 less than or equal to i less than or equal to \V(G)\, player A names a graph G(i) such that G(i) is isomorphic to a subgraph of G, \V(G(i))\ = i, and G(i-1) is an induced subgraph of G(i) if i > 1. Pla yer B must respond with a transitive orientation of G(i) which extends the transitive orientation given to G(i-1) in the previous round of p lay. Player A wins if and only if player B fails to give a transitive orientation to G(i) for some i, 1 less than or equal to i less than or equal to \V(G)\. Our main result shows that player A has at most thre e winning moves. We also discuss applications to on-line clique coveri ng of comparability graphs, and we mention some open problems.