A linear systolic algorithm for the connected component problem

DOI10.1007/BF01952677zbMATH Open0677.68001MaRDI QIDQ1123585FDOQ1123585

Authors: Ming-Shin Tsai, Shing-Tsaan Huang 

Publication date: 1989

Published in: BIT (Search for Journal in Brave)

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

zbMATH Keywords

graphsystolic algorithmconnected component problem

Mathematics Subject Classification ID

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

Cites Work

• Efficiency of a Good But Not Linear Set Union Algorithm
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• An O(logn) parallel connectivity algorithm
• Finding Connected Components and Connected Ones on a Mesh-Connected Parallel Computer
• Computing connected components on parallel computers
• Title not available (Why is that?)
• A Systolic Design for Connectivity Problems
• 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
• Comparative study and proof of single-pass connected components algorithms
• Title not available (Why is that?)

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)