%0 Book Section %1 Shi1995Optimal %A Shi, Weiping %A West, Douglas %D 1995 %J Computing and Combinatorics %K graphs math %P 131--140 %R 10.1007/bfb0030827 %T Optimal algorithms for finding connected components of an unknown graph %U http://dx.doi.org/10.1007/bfb0030827 %X 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 SV, and the oracle tells us the vertices connected to S. 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 O(mink,log n) queries and a randomized algorithm using expected O(mink, log k+log log n) queries. We also prove matching lower bounds.

@incollection{Shi1995Optimal, abstract = {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 SV, and the oracle tells us the vertices connected to S. 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 O(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.}, added-at = {2018-12-02T16:09:07.000+0100}, author = {Shi, Weiping and West, Douglas}, biburl = {https://www.bibsonomy.org/bibtex/216ff49ab830dfd6de1a6130fb8766f40/karthikraman}, citeulike-article-id = {6284023}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/bfb0030827}, citeulike-linkout-1 = {http://www.springerlink.com/content/m20jv45431114236}, doi = {10.1007/bfb0030827}, interhash = {a4e5a06396f5a2d6c8914b15fc6ddfd1}, intrahash = {16ff49ab830dfd6de1a6130fb8766f40}, journal = {Computing and Combinatorics}, keywords = {graphs math}, pages = {131--140}, posted-at = {2009-12-02 13:22:16}, priority = {2}, timestamp = {2018-12-02T16:09:07.000+0100}, title = {Optimal algorithms for finding connected components of an unknown graph}, url = {http://dx.doi.org/10.1007/bfb0030827}, year = 1995 }