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


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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

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

citation count

  • 1

complete list of authors

  • Shi, Weiping||West, Douglas B

publication date

  • January 1995