Computing the Weak Components of a Directed Graph
Author:
- Jean Francois PacaultJPJean Francois Pacault
- 1 March 1974
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 3 (1) , 56-61
Abstract
The weak components of a directed graph G are defined as follows: two vertices u and v of G belong to the same weak component if there is a directed path from u to v and from v to u (then u and v belong to the same strong component) or if one can go from u to v and back through a sequence of “nonpath” steps. The weak components can be determined with an algorithm involving O(max (number of vertices, number of edges)) computation time. The algorithm first determines a partition $C_1 , \cdots ,C_p $ of the set V of vertices of G such that the weak components are the unions of $C_i $’s of consecutive subscripts, and then groups consecutive $C_i $’s together to form the weak components.
Keywords
This publication has 2 references indexed in Scilit:
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Complements and transitive closuresDiscrete Mathematics, 1972