A linear systolic algorithm for the connected component problem

DOI10.1007/BF01952677MaRDI QIDQ1123585zbMATH OpenFDO

Authors Ming-Shin Tsai, Shing-Tsaan Huang

Publication date 1989

Published in BIT (Search for Journal in Brave)

zbMATH Keywords

graphsystolic algorithmconnected component problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Theory of software (68N99)

Recommendations

• Determining connected components in linear time by a linear number of processors
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• scientific article; zbMATH DE number 1751891
• scientific article; zbMATH DE number 3930349
• A fully-pipelined systolic algorithm for finding bridges on an undirected connected graph

Cites work

• scientific article; zbMATH DE number 3905859 (Why is no real title available?)
• A Systolic Design for Connectivity Problems
• An O(logn) parallel connectivity algorithm
• Computing connected components on parallel computers
• Efficiency of a Good But Not Linear Set Union Algorithm
• Finding Connected Components and Connected Ones on a Mesh-Connected Parallel Computer
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• VLSI Algorithms for the Connected Component Problem

Cited in

(4)

• Efficient systolic algorithm for finding bridges in a connected graph
• A fully-pipelined systolic algorithm for finding bridges on an undirected connected graph
• scientific article; zbMATH DE number 3950240 (Why is no real title available?)
• Comparative study and proof of single-pass connected components algorithms

This page was built for publication: A linear systolic algorithm for the connected component problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123585)