Talk:Maximal elements algorithms

As far as I know, Kosaraju's algorithm finds the "strongly connected components" of a directed graph. But the Schwartz set is not identical to the "strongly connected components", but to the "communicating classes" of a directed graph.

A strongly connected component SCC is a set of knots with the following property:

1. If knot A is in SCC and knot B is in SCC \ {A}, then there is a directed path from knot A to knot B, that consists only of knots in SCC, and a directed path from knot B to knot A, that consists only of knots in SCC.

On the other side, a communicating class CC is a set of knots with the following properties:

1. If knot A is in CC and knot B is in CC \ {A}, then there is a directed path from knot A to knot B and a directed path from knot B to knot A.
2. If knot A is in CC and there is a directed path from knot B to knot A, then also knot B is in CC.

Markus Schulze 04:44, 27 October 2006 (PDT)

Isn't the Beats and Beats-or-ties relation for Smith and Schwartz the wrong way around? The maximal element for Beat is the set whose members beat everybody outside of it -- that's Smith. And the maximal element of Beat-or-tie is the set whose members beat or tie everybody outside of it -- that's Schwartz, if I'm not mistaken. Because Beat-or-tie is more lenient than Beat, the set can be smaller (can exclude more candidates)... and the Schwartz set is a subset of the Smith set. Kristomun (talk) 23:27, 25 January 2020 (UTC)