Talk:Maximal elements algorithms

From Electowiki
Revision as of 04:44, 27 October 2006 by MarkusSchulze (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 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 knot B is also in CC.

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