Determining connected components in linear time by a linear number of processors

DOI10.1016/0020-0190(87)90219-5zbMath0653.68066OpenAlexW2041451693MaRDI QIDQ1108033

Ferdinand Peper

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90219-5

zbMATH Keywords

connected componentsparallel algorithmtransitive closureSIMDsimple undirected graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
• Parallel algorithms for the connected components and minimal spanning tree problems
• Computing connected components on parallel computers
• The Parallel Recognition of Classes of Graphs
• Parallel Matrix and Graph Algorithms
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Efficient parallel algorithms for some graph problems
• Cellular arrays for the solution of graph problems

This page was built for publication: Determining connected components in linear time by a linear number of processors