{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:10:50Z","timestamp":1778249450022,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602163","type":"print"},{"value":"9783540447337","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030827","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"131-140","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal algorithms for finding connected components of an unknown graph"],"prefix":"10.1007","author":[{"given":"Weiping","family":"Shi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas B.","family":"West","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"issue":"8","key":"14_CR1","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1109\/31.192423","volume":"36","author":"C. C. Chen","year":"1989","unstructured":"C. C. Chen and F. Hwang. Detecting and locating electrical shorts using group testing. IEEE Trans. on Circuits and Systems 36 (8), pp. 1113\u20131116, Aug. 1989.","journal-title":"IEEE Trans. on Circuits and Systems"},{"issue":"9","key":"14_CR2","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1109\/43.160002","volume":"11","author":"W.-T. Cheng","year":"1992","unstructured":"W.-T. Cheng, J. L. Lewandowski and E. Wu. Optimal diagnostic methods for wiring interconnects. IEEE Trans. on Computer-Aided Design 11 (9), pp. 1161\u20131166, Sept. 1992.","journal-title":"IEEE Trans. on Computer-Aided Design"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"A. Fiat, D. P. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive algorithms for layered graph traversal. FOCS, pp. 288\u2013297, 1991.","DOI":"10.1109\/SFCS.1991.185381"},{"issue":"10","key":"14_CR4","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1109\/TCS.1976.1084138","volume":"23","author":"M. Garey","year":"1976","unstructured":"M. Garey, D. Johnson, and H. So. An application of graph coloring to printed circuit testing. IEEE Trans. Circuits and Systems 23 (10), pp. 591\u2013599, Oct. 1976.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"N. Jarwala and C. W. Yau. A new framework for analyzing test generation and diagnosis algorithms for wiring interconnect. Proc. International Testing Conference, pp. 63\u201370, 1989.","DOI":"10.1109\/TEST.1989.82278"},{"issue":"6","key":"14_CR6","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1145\/195613.195632","volume":"41","author":"R. M. Karp","year":"1994","unstructured":"R. M. Karp. Probabilistic recurrence relations. J. of ACM 41 (6), Nov. 1994, pp. 1136\u20131150.","journal-title":"J. of ACM"},{"issue":"4","key":"14_CR7","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1109\/T-C.1974.223950","volume":"23","author":"W. H. Kautz","year":"1973","unstructured":"W. H. Kautz. Testing for faults in wiring networks. IEEE Trans. on Computers, 23 (4), pp. 358\u2013363, April 1973.","journal-title":"IEEE Trans. on Computers"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"L. Kavraki, J.-C. Latombe, R. Motwani and P. Raghavan. Randomized query processing in robot motion planning. STOC, 1995.","DOI":"10.21236\/ADA326821"},{"key":"14_CR9","unstructured":"W. Shi and W. K. Fuchs. Optimal interconnect diagnosis of wiring networks. To appear IEEE Trans. on VLSI Systems, Sept. 1995."},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"A. Yao, Probabilistic Computations: Towards a Unified Measure of Complexity. Proc. FOCS, pp. 222\u2013227, 1977.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T13:16:42Z","timestamp":1778246202000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0030827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0030827","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}