Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs
Weiping Shi, Douglas B. West · SIAM Journal on Computing · 1999
We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set $S \subseteq V$\hspace*{-1pt}, and the oracle tells us the vertices connected to S. The objective is to use the minimum number of queries to partition the vertex set into components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. We present a deterministic algorithm using O(min{k, lg n}) queries and a randomized algorithm using expected O(min{k,lg k + lg lg n}) queries, where n is the number of vertices and k is the number of components. We also prove matching lower bounds.