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.
SIAM Journal on Discrete Mathematics
author list (cited authors)
complete list of authors
Shi, Weiping||West, Douglas B