On-line algorithms for ordered sets and comparability graphs Original Research Article

We discuss several results concerning on-line algorithms for ordered sets and comparability graphs. The main new result is on the problem of on-line transitive orientation. We view on-line transitive orientation of a comparability graph G as a two-person game. In the ith round of play, 1 ⩽ i ⩽ | V(G)|, player A names a graph Gi such that Gi is isomorphic to a subgraph of G, |V(Gi)| = i, and Gi−1 is an induced subgraph of Gi if i > 1. Player B must respond with a transitive orientation of Gi which extends the transitive orientation given to Gi−1 in the previous round of play. Player A wins if and only if player B fails to give a transitive orientation to Gi for some i, 1 ⩽ i ⩽ |V(G)|. Our main result shows that player A has at most three winning moves. We also discuss applications to on-line clique covering of comparability graphs, and we mention some open problems.