Optimal Algorithms for Finding Connected Components of an Unknown Graph
作者： Weiping Shi , Douglas B. West
DOI: 10.1007/BFB0030827
关键词: k-edge-connected graph 、 Modular decomposition 、 Strongly connected component 、 Combinatorics 、 Connected component 、 Mathematics 、 Discrete mathematics 、 Kosaraju's algorithm 、 Vertex (geometry) 、 Tarjan's strongly connected components algorithm 、 In-place algorithm
摘要: We want to find the connected components of an unknown graph G with a known vertex set V. learn about by sending oracle query S⊂V, and tells us vertices S. use minimum number queries, adaptively, components. The problem is also as interconnect diagnosis wiring networks in VLSI. has n k components, but not part input. present deterministic algorithm using O(min{k,log n}) queries randomized expected O(min{k, log k+log queries. prove matching lower bounds.
springer.com
sci-hub.se 参考文章(10)
Richard M. Karp, Probabilistic recurrence relations Journal of the ACM. ,vol. 41, pp. 1136- 1150 ,(1994) , 10.1145/195613.195632
W.H. Kautz, Testing for Faults in Wiring Networks IEEE Transactions on Computers. ,vol. 23, pp. 358- 363 ,(1974) , 10.1109/T-C.1974.223950
C.C. Chen, F.K. Hwang, Detecting and locating electrical shorts using group testing IEEE Transactions on Circuits and Systems. ,vol. 36, pp. 1113- 1116 ,(1989) , 10.1109/31.192423
Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Prabhakar Raghavan, Randomized query processing in robot path planning symposium on the theory of computing. pp. 353- 362 ,(1995) , 10.1145/225058.225159
Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 222- 227 ,(1977) , 10.1109/SFCS.1977.24
M. Garey, D. Johnson, Hing So, An application of graph coloring to printed circuit testing IEEE Transactions on Circuits and Systems. ,vol. 23, pp. 591- 599 ,(1976) , 10.1109/TCS.1976.1084138
N. Jarwala, C.W. Yau, A new framework for analyzing test generation and diagnosis algorithms for wiring interconnects international test conference. pp. 63- 70 ,(1989) , 10.1109/TEST.1989.82278
W.-T. Cheng, J.L. Lewandowski, E. Wu, Optimal diagnostic methods for wiring interconnects IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 11, pp. 1161- 1166 ,(1992) , 10.1109/43.160002
Weiping Shi, W.K. Fuchs, Optimal interconnect diagnosis of wiring networks IEEE Transactions on Very Large Scale Integration Systems. ,vol. 3, pp. 430- 436 ,(1995) , 10.1109/92.407000
A. Fiat, D.P. Foster, H. Karloff, Y. Rabani, Y. Ravid, S. Viswanathan, Competitive algorithms for layered graph traversal [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. pp. 288- 297 ,(1991) , 10.1109/SFCS.1991.185381