Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs

DOI10.1137/S0097539795288118zbMath0928.68056OpenAlexW2065008615MaRDI QIDQ4268721

Weiping Shi, Douglas B. West

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795288118

zbMATH Keywords

graphrandomized algorithmlower boundfault diagnosiscomponentconnection class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Fault detection; testing in circuits and networks (94C12) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

This page was built for publication: Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs