Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs Academic Article uri icon


  • 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 qq V, 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.

author list (cited authors)

  • Shi, W., & West, D. B.

citation count

  • 1

publication date

  • January 1999