- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnlilne Submission ㆍMy Manuscript - For Reviewers - For Editors
 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 Published online 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. Keywords : strongly connected components, directed graph, inverse matrix, diagonally dominant matrix MSC numbers : 05C20, 05C50, 65F05 Full-Text :