Recognition of strongly connected components by the location of nonzero elements occurring in $C(G) = (D-A(G))^{-1}$
Bull. Korean Math. Soc. 2004 Vol. 41, No. 1, 125-135 Printed March 1, 2004
Koonchan Kim and Youngyug Kang Keimyung University, Keimyung University
Abstract : One of the intriguing and fundamental algorithmic gra-ph problems is the computation of the strongly connected components of a directed graph $G$. In this paper we first introduce a simple procedure for determining the location of the nonzero elements occurring in $B^{-1}$ without fully inverting $B$, where $B \equiv (b_{ij})$ and $B^{T}$ are diagonally dominant matrices with $b_{ii} > 0$ for all $i$ and $b_{ij} \leq 0$, for $i \neq j$, and then, as an application, show that all of the strongly connected components of a directed graph $G$ can be recognized by the location of the nonzero elements occurring in the matrix $C(G) = (D - A(G))^{-1}$. Here $A(G)$ is an adjacency matrix of $G$ and $D$ is an arbitrary scalar matrix such that $(D - A(G))$ becomes a diagonally dominant matrix.
