{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:03Z","timestamp":1759638663839},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_31","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T13:41:33Z","timestamp":1155649293000},"page":"284-298","source":"Crossref","is-referenced-by-count":7,"title":["The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm"],"prefix":"10.1007","author":[{"given":"Ying","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoforos","family":"Hadjicostis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krishnaiyan","family":"Thulasiraman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"Bollob\u00e1s, B.: Random graphs. Academic Press Inc., London (1985)"},{"doi-asserted-by":"crossref","unstructured":"Brodie, M., Rish, I., Ma, S.: Optimizing probe selection for fault localization. In: International Workshop on Distributed Systems: Operations and Management (2001)","key":"31_CR2","DOI":"10.3990\/2.9"},{"doi-asserted-by":"crossref","unstructured":"Das, A., Thulasiraman, K.: Diagnosis of t\/s-diagnosable systems. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 193\u2013205 (1990)","key":"31_CR3","DOI":"10.1007\/3-540-52292-1_3"},{"issue":"5","key":"31_CR4","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1137\/S0097539790187539","volume":"23","author":"A. Das","year":"1994","unstructured":"Das, A., Thulasiraman, K., Agarwal, V.: Diagnosis of t\/(t+1)-diagnosable systems. SIAM J. Comput.\u00a023(5), 895\u2013905 (1994)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Frieze, A., Martin, R., Moncel, J., Ruszink\u00f3and, K., Smyth, C.: Codes identifying sets of vertices in random networks. (submitted for publication, 2005)","key":"31_CR5","DOI":"10.1109\/ISIT.2005.1523586"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/3-540-44676-1_13","volume-title":"Algorithms - ESA 2001","author":"B.V. Halld\u00f3rsson","year":"2001","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Ravi, R.: On the approximability of the minimum test collection problem. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 158\u2013169. Springer, Heidelberg (2001)"},{"key":"31_CR7","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., Luczak, T., Rucinski, A.: Random graphs. Wiley, New York (2000)"},{"issue":"3-4","key":"31_CR8","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<467::AID-RSA15>3.0.CO;2-W","volume":"13","author":"S. Janson","year":"1998","unstructured":"Janson, S.: New versions of Suen\u2019s correlation inequality. Random Struct. Algorithms\u00a013(3-4), 467\u2013483 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"31_CR9","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/18.661507","volume":"44","author":"M. Karpovsky","year":"1998","unstructured":"Karpovsky, M., Chakrabarty, K., Levitin, L.: On a new class of codes for identifying vertices in graphs. IEEE Trans. on Information Theory\u00a044(2), 599\u2013611 (1998)","journal-title":"IEEE Trans. on Information Theory"},{"doi-asserted-by":"crossref","unstructured":"Laifenfeld, M., Trachtenberg, A.: Disjoint identifying-codes for arbitrary graphs. In: IEEE Symposium on Information Theory (submitted, 2005)","key":"31_CR10","DOI":"10.1109\/ISIT.2005.1523331"},{"issue":"3","key":"31_CR11","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1006\/eujc.2002.0571","volume":"23","author":"T. Laihonen","year":"2002","unstructured":"Laihonen, T.: Optimal codes for strong identification. Eur. J. Comb.\u00a023(3), 307\u2013313 (2002)","journal-title":"Eur. J. Comb."},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1109\/PGEC.1967.264748","volume":"16","author":"F. Preparata","year":"1967","unstructured":"Preparata, F., Metze, G., Chien, R.: On the connection assignment problem of diagnosiable systems. IEEE Trans. on Electronic Computers\u00a016, 848\u2013854 (1967)","journal-title":"IEEE Trans. on Electronic Computers"},{"doi-asserted-by":"crossref","unstructured":"Ray, S., Ungrangsi, R., Pellegrini, F., Trachtenberg, A., Starobinski, D.: Robust location detection in emergency sensor networks. In: INFOCOM (2003)","key":"31_CR13","DOI":"10.1109\/INFCOM.2003.1208941"},{"issue":"2","key":"31_CR14","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/rsa.3240010210","volume":"1","author":"S. Suen","year":"1990","unstructured":"Suen, S.: A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph. Random Struct. Algorithms\u00a01(2), 231\u2013242 (1990)","journal-title":"Random Struct. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:13:43Z","timestamp":1605644023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11809678_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}