Static and dynamic parallel computation of connected components
type: Item
instance of: scholarly article
title: Static and dynamic parallel computation of connected components
zbMATH Open document ID: 0803.68088
DOI: 10.1016/0020-0190(94)00016-6
published in: Information Processing Letters
publication date: 1994-05-05T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 562520
zbMATH Keywords: parallel algorithms
zbMATH Keywords: work-optimality
zbMATH Keywords: sparsification
zbMATH Keywords: connected components
zbMATH Keywords: undirected graph
zbMATH Keywords: EREW model
zbMATH Keywords: tree data structure
author: Paolo Ferragina
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00016-6
OpenAlex ID: W2053942345
cites work: Efficient parallel algorithms for some graph problems
cites work: Q3140396
cites work: Sparsification—a technique for speeding up dynamic graph algorithms
cites work: Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
cites work: An efficient and fast parallel-connected component algorithm
cites work: Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
cites work: Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
cites work: Parallel algorithms for the connected components and minimal spanning tree problems
cites work: An O(log n) algorithm for parallel update of minimum spanning trees
cites work: An O(logn) parallel connectivity algorithm
description: scientific article; zbMATH DE number 562520