Optimal algorithms for finding connected components of an unknown graph Conference Paper uri icon

abstract

  • © 1995, Springer-Verlag. All Rights Reserved. We want to find the connected components of an unknown graph G with a known vertex set V. We learn about G by sending an oracle a query set S ⊆ V, and the oracle tells us the vertices connected to We want to use the minimum number of queries, adaptively, to find the components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. The graph has n vertices and k components, but k is not part of the input. We present a deterministic algorithm using 0(min{k:, log n}) queries and a randomized algorithm using expected O(min{k, log k + log log n}) queries. We also prove matching lower bounds.

author list (cited authors)

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

citation count

  • 1

publication date

  • January 1995