{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T12:51:29Z","timestamp":1725540689014},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642359255"},{"type":"electronic","value":"9783642359262"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-35926-2_4","type":"book-chapter","created":{"date-parts":[[2012,12,21]],"date-time":"2012-12-21T04:32:11Z","timestamp":1356064331000},"page":"32-45","source":"Crossref","is-referenced-by-count":0,"title":["On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths"],"prefix":"10.1007","author":[{"given":"Florent","family":"Foucaud","sequence":"first","affiliation":[]},{"given":"Matja\u017e","family":"Kov\u0161e","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Auger, D., Charon, I., Hudry, O., Lobstein, A.: Watching systems in graphs: an extension of identifying codes. Discrete Appl. Math. (in press)"},{"key":"4_CR2","unstructured":"Berger-Wolf, T.Y., Laifenfeld, M., Trachtenberg, A.: Identifying codes and the set cover problem. In: Proc. 44th Annual Allerton Conference on Communication, Control and Computing (September 2006)"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0095-8956(72)90025-1","volume":"12","author":"J.A. Bondy","year":"1972","unstructured":"Bondy, J.A.: Induced subsets. J. Comb. Theory B\u00a012(2), 201\u2013202 (1972)","journal-title":"J. Comb. Theory B"},{"issue":"2","key":"4_CR4","first-page":"403","volume":"4","author":"I. Charon","year":"2008","unstructured":"Charon, I., Cohen, G., Hudry, O., Lobstein, A.: Discriminating codes in bipartite graphs. Adv. Math. Commun.\u00a04(2), 403\u2013420 (2008)","journal-title":"Adv. Math. Commun."},{"key":"4_CR5","doi-asserted-by":"crossref","first-page":"16","DOI":"10.37236\/934","volume":"14","author":"I. Charon","year":"2007","unstructured":"Charon, I., Honkala, I., Hudry, O., Lobstein, A.: Structural properties of twin-free graphs. Electron. J. Comb.\u00a014, R16 (2007)","journal-title":"Electron. J. Comb."},{"issue":"8","key":"4_CR6","doi-asserted-by":"publisher","first-page":"2192","DOI":"10.1109\/TIT.2002.800490","volume":"48","author":"I. Charon","year":"2002","unstructured":"Charon, I., Hudry, O., Lobstein, A.: Identifying and locating-dominating codes: NP-completeness results for directed graphs. IEEE T. Inform. Theory\u00a048(8), 2192\u20132200 (2002)","journal-title":"IEEE T. Inform. Theory"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci.\u00a0354, 320\u2013338 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"K.M.J. Bontridder De","year":"2003","unstructured":"De Bontridder, K.M.J., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Math. Program. B\u00a098, 477\u2013491 (2003)","journal-title":"Math. Program. B"},{"issue":"4","key":"4_CR9","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1016\/j.ejc.2011.01.002","volume":"32","author":"F. Foucaud","year":"2011","unstructured":"Foucaud, F., Guerrini, E., Kov\u0161e, M., Naserasr, R., Parreau, A., Valicov, P.: Extremal graphs for the identifying code problem. Eur. J. Combin.\u00a032(4), 628\u2013638 (2011)","journal-title":"Eur. J. Combin."},{"key":"4_CR10","unstructured":"Foucaud, F., Gravier, S., Naserasr, R., Parreau, A., Valicov, P.: Identifying codes in line graphs. To appear in J. Graph Theor."},{"key":"4_CR11","unstructured":"Foucaud, F., Naserasr, R., Parreau, A.: Characterizing extremal digraphs for identifying codes and extremal cases of Bondy\u2019s theorem on induced subsets. Graphs Comb. (in press)"},{"issue":"9-10","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1016\/j.disc.2006.07.041","volume":"307","author":"A. Frieze","year":"2007","unstructured":"Frieze, A., Martin, R., Moncel, J., Ruszink\u00f3, M., Smyth, C.: Codes identifying sets of vertices in random networks. Discrete Math.\u00a0307(9-10), 1094\u20131107 (2007)","journal-title":"Discrete Math."},{"key":"4_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"issue":"2-3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1016\/S0166-218X(02)00579-6","volume":"129","author":"I. Honkala","year":"2003","unstructured":"Honkala, I., Karpovsky, M., Litsyn, S.: Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori. Discrete Appl. Math.\u00a0129(2-3), 409\u2013419 (2003)","journal-title":"Discrete Appl. Math."},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR16","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.B.: On a new class of codes for identifying vertices in graphs. IEEE T. Inform. Theory\u00a044, 599\u2013611 (1998)","journal-title":"IEEE T. Inform. Theory"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Laifenfeld, M., Trachtenberg, A., Cohen, R., Starobinski, D.: Joint monitoring and routing in wireless sensor networks using robust identifying codes. In: Proc. IEEE Broadnets 2007, pp. 197\u2013206 (September 2007)","DOI":"10.1109\/BROADNETS.2007.4550425"},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1137\/0906067","volume":"6","author":"B.M.E. Moret","year":"1985","unstructured":"Moret, B.M.E., Shapiro, H.D.: On minimizing a set of tests. SIAM J. Sci. Stat. Comp.\u00a06(4), 983\u20131003 (1985)","journal-title":"SIAM J. Sci. Stat. Comp."},{"key":"4_CR19","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley (1994)"},{"key":"4_CR20","first-page":"1","volume":"10","author":"P. Rosendahl","year":"2003","unstructured":"Rosendahl, P.: On the identification of vertices using cycles. Electron. J. Comb.\u00a010, P1 (2003)","journal-title":"Electron. J. Comb."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35926-2_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:33:54Z","timestamp":1620135234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35926-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642359255","9783642359262"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35926-2_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}