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

abstract

  • 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)

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

citation count

  • 0

publication date

  • January 2001