Structural Diagnosis of Wiring Networks: Finding Connected Components of Unknown Subgraphs
- Additional Document Info
- View All
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.
author list (cited authors)