strongly connected component


Also found in: Acronyms, Wikipedia.

strongly connected component

(SCC) A subset, S, of the nodes of a directed graph such that any node in S is reachable from any other node in S and S is not a subset of any larger such set. SCCs are equivalence classes under the transitive closure of the "directly connected to" relation.
Mentioned in ?
References in periodicals archive ?
Since the automaton is finite, there are a terminal strongly connected component S' [member of] [?
0], w) [member of] S' and S' is a terminal strongly connected component, Inf (A; [xi]) [subset or equal to] [S.
A Web-based social network, on the other hand, considers many complex structures like cycles, nested cycles, strongly connected components etc.
show that the algorithm described above runs in time O(m[Alpha](m, n)+km), where k is the number of levels at which the strongly connected component algorithm had to be invoked.
The above procedure requires strongly connected component arc capacities to be at least 2[Delta] to route the total of [Delta] flow through.
Since the automaton is finite, there are a terminal strongly connected component S' [member of] T, a state s' [member of] S" and a v [member of] X* such that [delta](s", v) = s'.
The interval [x, x], by definition, is the strongly connected component of the vertex x in D.
In the definition of strongly connected component in Section 2, justification for a reachability operator has already been discussed.
25] to find a small vertex subset S [subset or equal to] W in G[W] with the property that every strongly connected component of G[W] - S has at most 3/4 [absolute value of W] vertices.
Its vertices are the strongly connected components [C.
Proposition 3 For every (multi)graph [GAMMA], there exists k such that every strongly connected component of [[GAMMA].
into its strongly connected components, and then taking the quotient digraph, (so two parts are connected by an arc if and only if there is an arc between the corresponding vertex sets in [?