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 :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd