Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set S qq V, and the oracle tells us the vertices connected to S. The objective is to use the minimum number of queries to partition the vertex set into components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. We present a deterministic algorithm using O(min{k, lg n}) queries and a randomized algorithm using expected O(min{k, lg k + lg lg n}) queries, where n is the number of vertices and k is the number of components. We also prove matching lower bounds.
