Bulletin of the
Korean Mathematical Society BKMS

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.

Keywords: strongly connected components, directed graph, inverse matrix, diagonally dominant matrix

MSC numbers: 05C20, 05C50, 65F05