Parallel Connectivity Algorithms
Loading...
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers Inc.
Open Access Color
Green Open Access
No
OpenAIRE Downloads
OpenAIRE Views
Publicly Funded
No
BIP! Indicators
Impulse
Average
Influence
Average
Popularity
Average
Abstract
We propose and implement two parallel algorithms to test the connectivity and find the connected components of a network in parallel. In both cases the connectivity matrix of the graph is partitioned to p processors. The first parallel algorithm (Alg. 2) processors test connectivity in their partitions and then cooperate to decide. The second parallel algorithm (Alg. 4) forms a labelled connectivity matrix and then partitions this matrix to processors to find the components of a disconnected graph. We show both algorithms achieve significant speedups even with only few processors. © 2023 Elsevier B.V. All rights reserved.
Description
Keywords
Connected Component, Connectivity, Network, Parallel Processing Systems, Connected Component, Connectivity, Connectivity Algorithms, Connectivity Matrix, Disconnected Graph, Network, Processor Test, Parallel Algorithms, Parallel processing systems, Connected component, Connectivity, Connectivity algorithms, Connectivity matrix, Disconnected graph, Network, Processor test, Parallel algorithms, Connectivity, Connected Component, Network
Fields of Science
Citation
WoS Q
Scopus Q
OpenCitations Citation Count
N/A
Source
3rd International Informatics and Software Engineering Conference IISEC 2022
Volume
Issue
Start Page
1
End Page
6
Collections
PlumX Metrics
Citations
Scopus : 0
Google Scholar™
