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

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.

authors

• Shi, Weiping

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

publisher

• Springer Nature  Publisher

published in

• Lecture Notes in Artificial Intelligence  Journal

Digital Object Identifier (DOI)

• 10.1007/bfb0030827

International Standard Book Number (ISBN) 10

• 354060216X

International Standard Book Number (ISBN) 13

• 9783540602163

start page

• 131

end page

• 140

volume

• 959

URL

• http://dx.doi.org/10.1007/bfb0030827