Structural Diagnosis of Wiring Networks: Finding Connected Components of Unknown Subgraphs Academic Article uri icon


  • Given a graph G = (V, ). we want to find the vertex sets of the components of an unknown subgraph F = (V. E) of G such that E . We learn about F by sending an oracle a query set S V, and the oracle tells us the vertices connected to S in F. The objective is to use the minimum number of queries to partition the vertex set V into components of F. In electronic circuit design, the problem is also known as structural diagnosis of wiring networks.

published proceedings

  • SIAM Journal on Discrete Mathematics

author list (cited authors)

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

citation count

  • 0

complete list of authors

  • Shi, Weiping||West, Douglas B

publication date

  • January 2001