A Granulation Strategy-Based Algorithm for Computing Strongly Connected Components in Parallel

Huixing He, Taihua Xu (), Jianjun Chen, Yun Cui and Jingjing Song
Additional contact information
Huixing He: School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212100, China
Taihua Xu: School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212100, China
Jianjun Chen: School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212100, China
Yun Cui: School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212100, China
Jingjing Song: School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212100, China

Mathematics, 2024, vol. 12, issue 11, 1-16

Abstract: Granular computing (GrC) is a methodology for reducing the complexity of problem solving and includes two basic aspects: granulation and granular-based computing. Strongly connected components (SCCs) are a significant subgraph structure in digraphs. In this paper, two new granulation strategies were devised to improve the efficiency of computing SCCs. Firstly, four SCC correlations between the vertices were found, which can be divided into two classes. Secondly, two granulation strategies were designed based on correlations between two classes of SCCs. Thirdly, according to the characteristics of the granulation results, the parallelization of computing SCCs was realized. Finally, a parallel algorithm based on granulation strategy for computing SCCs of simple digraphs named GPSCC was proposed. Experimental results show that GPSCC performs with higher computational efficiency than algorithms.

Keywords: strongly connected components; granulation strategy; SCCs correlations; parallel (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/11/1723/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/11/1723/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:11:p:1723-:d:1406714

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().