Anonymous user
Talk:Maximal elements algorithms: Difference between revisions
m
no edit summary
imported>MarkusSchulze No edit summary |
imported>MarkusSchulze mNo edit summary |
||
Line 1:
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
# 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:
# 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.
# If knot A is in CC and there is a directed path from knot B to knot A, then also knot B is
[[User:MarkusSchulze|Markus Schulze]] 04:44, 27 October 2006 (PDT)
| |||