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 ?
Let [??] [subset or equal to] T be the set of all strongly connected components terminal in T and F' = {[xi] : Inf(A; [xi]) [member of] [??]}.
The other kind of graph important for visibility based planners is the strongly connected component graph of the roadmap or its subgraphs.
It is a strongly connected component where all edges are of same type.
A b-balanced cut in a graph G = (V, E) is a cut that partitions the graph into connected components (strongly connected components in the directed case), each of which contains at most (1 - b) [multiplied by] n vertices, where n = |V|.
Consider any strongly connected component. Consider the vertex u of the component that is visited first during depth-first search.
Since s = [delta]([s.sub.0],w) [member of] S' and S" is a terminal strongly connected component, Inf(A; [xi]) [??] [S.sub.+].sub.
In general, one can consider strongly connected components of T(A).
In the first level, the structural properties of a graph are studied and strongly connected components are fused to reduce the original graph to a DAG.
The above procedure requires strongly connected component arc capacities to be at least 2[Delta] to route the total of [Delta] flow through.
It is obtained by partitioning [??] 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 [??]).
Otherwise, use the polynomial-time algorithm from [25, Corollary 2.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.sub.1], ...