Structural Diagnosis of Wiring Networks: Finding Connected Components of Unknown Subgraphs

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.

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