Content deleted Content added
→The method of conditional probabilities using pessimistic estimators: deleted an extra sign |
→Algorithm maximizing the pessimistic estimator: added a spacebar |
||
Line 137:
The algorithm below chooses each vertex ''u'' to maximize the resulting pessimistic estimator. By the previous considerations, this keeps the pessimistic estimator from decreasing and guarantees a successful outcome.
Below, ''N''<sup>(''t'')</sup>(''u'') denotes the neighbors of ''u'' in ''R''<sup>(''t'')</sup> (that is, neighbors of ''u'' that are neither in ''S'' nor have a neighbor in ''S'').
1. Initialize ''S'' to be the empty set.
2. While there exists a not-yet-considered vertex ''u'' with no neighbor in ''S'':
| |||