Optimal algorithms for finding connected components of an unknown graph

DOI10.1007/BFB0030827MaRDI QIDQ6085701zbMATH OpenOpenAlexFDO

Authors Weiping Shi, Douglas B. West

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030827

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs
• Structural diagnosis of wiring networks: Finding connected components of unknown subgraphs
• On the Complexity of Finding an Unknown Cut Via Vertex Queries
• Estimating the number of connected components in sublinear time
• An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph

Cites work

• An application of graph coloring to printed circuit testing
• scientific article; zbMATH DE number 1263211 (Why is no real title available?)
• Probabilistic recurrence relations
• Testing for Faults in Wiring Networks

Cited in

(3)

• Finding strongly connected components of simple digraphs based on granulation strategy
• Parameterized algorithms for finding highly connected solution
• Parameterized algorithms for finding highly connected solution

This page was built for publication: Optimal algorithms for finding connected components of an unknown graph

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