Computer Science 789 Online Algorithms

Hint 4 for the Proof of the Game Graph Lemma

Getting a behavioral strategy S from a path set strategy P.

Note! The old version of the Fourth Hint is incorrect!

If P is a path strategy, let S be the behavioral strategy defined as follows.

For any red node x, Let alpha be the minimum weight member of P which ends at x. By one of the conditions of a path strategy, there must exist a node y such that there is an edge (x,y) and such that beta = alpha(x,y) is a member of P.

Let S(x) = y.

Back to Course Page

Back to Assignment Page

Back to Assignment 1