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.

published proceedings

  • SIAM Journal on Computing

author list (cited authors)

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

citation count

  • 1

complete list of authors

  • Shi, Weiping||West, Douglas B

publication date

  • January 1999