{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T01:23:37Z","timestamp":1725758617618},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642452772"},{"type":"electronic","value":"9783642452789"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45278-9_14","type":"book-chapter","created":{"date-parts":[[2013,11,25]],"date-time":"2013-11-25T10:35:18Z","timestamp":1385375718000},"page":"150-163","source":"Crossref","is-referenced-by-count":6,"title":["The Complexity of the Identifying Code Problem in Restricted Graph Classes"],"prefix":"10.1007","author":[{"given":"Florent","family":"Foucaud","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"14_CR1","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1016\/j.ejc.2009.11.012","volume":"31","author":"D. Auger","year":"2010","unstructured":"Auger, D.: Minimal identifying codes in trees and planar graphs with large girth. Eur. J. Combin.\u00a031(5), 1372\u20131384 (2010)","journal-title":"Eur. J. Combin."},{"issue":"6","key":"14_CR2","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1111\/j.1475-3995.2009.00750.x","volume":"17","author":"D. Auger","year":"2010","unstructured":"Auger, D., Charon, I., Hudry, O., Lobstein, A.: Complexity results for identifying codes in planar graphs. Int. T. Oper. Res.\u00a017(6), 691\u2013710 (2010)","journal-title":"Int. T. Oper. Res."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"issue":"1","key":"14_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"14_CR5","unstructured":"Berger-Wolf, T.Y., Laifenfeld, M., Trachtenberg, A.: Identifying codes and the set cover problem. In: Proc. 44th Allerton Conf. on Comm. Contr. and Comput. (2006)"},{"issue":"1","key":"14_CR6","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"K.S. Booth","year":"1982","unstructured":"Booth, K.S., Johnson, H.J.: Dominating sets in chordal graphs. SIAM J. Comput.\u00a011(1), 191\u2013199 (1982)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"14_CR7","doi-asserted-by":"publisher","first-page":"403","DOI":"10.3934\/amc.2008.2.403","volume":"4","author":"E. Charbit","year":"2008","unstructured":"Charbit, E., Charon, I., Cohen, G., Hudry, O., Lobstein, A.: Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Adv. Math. Commun.\u00a04(2), 403\u2013420 (2008)","journal-title":"Adv. Math. Commun."},{"issue":"1-3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math.\u00a086(1-3), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"issue":"3","key":"14_CR9","doi-asserted-by":"publisher","first-page":"2109","DOI":"10.1016\/S0304-3975(02)00536-4","volume":"290","author":"I. Charon","year":"2003","unstructured":"Charon, I., Hudry, O., Lobstein, A.: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theor. Comput. Sci.\u00a0290(3), 2109\u20132120 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-006-7908-0","volume":"11","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of edge dominating set problems. J. Comb. Optim.\u00a011, 279\u2013290 (2006)","journal-title":"J. Comb. Optim."},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M. Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inform. Comput.\u00a0206, 1264\u20131275 (2008)","journal-title":"Inform. Comput."},{"key":"14_CR12","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. Programm. Ser. B\u00a098, 477\u2013491 (2003)","journal-title":"Math. Programm. Ser. B"},{"key":"14_CR13","unstructured":"De Ridder, H.N., et al.: Information System on Graph Classes and their Inclusions (ISGCI), http:\/\/www.graphclasses.org"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M. Farber","year":"1985","unstructured":"Farber, M., Keil, J.M.: Domination in permutation graphs. J. Algorithm.\u00a06, 309\u2013321 (1985)","journal-title":"J. Algorithm."},{"key":"14_CR15","unstructured":"Foucaud, F.: Combinatorial and algorithmic aspects of identifying codes in graphs. PhD thesis, Universit\u00e9 Bordeaux 1, France (2012), http:\/\/tel.archives-ouvertes.fr\/tel-00766138"},{"key":"14_CR16","unstructured":"Foucaud, F.: On the decision and approximation complexities for identifying codes and locating-dominating sets in restricted graph classes (2013) (manuscript), http:\/\/www-ma4.upc.edu\/~florent.foucaud\/Research"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1002\/jgt.21686","volume":"73","author":"F. Foucaud","year":"2013","unstructured":"Foucaud, F., Gravier, S., Naserasr, R., Parreau, A., Valicov, P.: Identifying codes in line graphs. J. Graph Theor.\u00a073(4), 425\u2013448 (2013), doi:10.1002\/jgt.21686","journal-title":"J. Graph Theor."},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., Valicov, P.: Identifying codes in subclasses of perfect graphs. Manuscript (2012)","DOI":"10.1002\/jgt.21686"},{"issue":"4","key":"14_CR19","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"14_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman (1979)"},{"issue":"1","key":"14_CR21","first-page":"43","volume":"3","author":"S. Gravier","year":"2008","unstructured":"Gravier, S., Klasing, R., Moncel, J.: Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs. Alg. Oper. Res.\u00a03(1), 43\u201350 (2008)","journal-title":"Alg. Oper. Res."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.): Domination in graphs: advanced topics. Marcel Dekker (1998)","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"14_CR23","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs. J. Algor.\u00a026, 238\u2013274 (1998)","journal-title":"J. Algor."},{"key":"14_CR24","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. Sys. Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. Comput. Sys. Sci."},{"key":"14_CR25","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/18.661507","volume":"44","author":"M.G. Karpovsky","year":"1998","unstructured":"Karpovsky, M.G., 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"},{"issue":"9","key":"14_CR26","doi-asserted-by":"publisher","first-page":"3929","DOI":"10.1109\/TIT.2008.928263","volume":"54","author":"M. Laifenfeld","year":"2008","unstructured":"Laifenfeld, M., Trachtenberg, A.: Identifying codes and covering problems. IEEE T. Inform. Theory\u00a054(9), 3929\u20133950 (2008)","journal-title":"IEEE T. Inform. Theory"},{"key":"14_CR27","unstructured":"Lobstein, A.: Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography, http:\/\/www.infres.enst.fr\/~lobstein\/debutBIBidetlocdom.pdf"},{"key":"14_CR28","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H. M\u00fcller","year":"1987","unstructured":"M\u00fcller, H., Brandt\u00e4dt, A.: The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs. Theor. Comput. Sci.\u00a053, 257\u2013265 (1987)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"14_CR29","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1017\/S0963548309990344","volume":"18","author":"T. M\u00fcller","year":"2009","unstructured":"M\u00fcller, T., Sereni, J.-S.: Identifying and locating-dominating codes in (random) geometric networks. Comb. Probab. Comput.\u00a018(6), 925\u2013952 (2009)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"14_CR30","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Sys. Sci.\u00a043(3), 425\u2013440 (1991)","journal-title":"J. Comput. Sys. Sci."},{"key":"14_CR31","first-page":"97","volume":"45","author":"P.J. Slater","year":"1984","unstructured":"Slater, P.J., Rall, D.F.: On location-domination numbers for certain classes of graphs. Congr. Numer.\u00a045, 97\u2013106 (1984)","journal-title":"Congr. Numer."},{"issue":"1","key":"14_CR32","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.ipl.2007.02.001","volume":"103","author":"J. Suomela","year":"2007","unstructured":"Suomela, J.: Approximability of identifying codes and locating-dominating codes. Inform. Process. Lett.\u00a0103(1), 28\u201333 (2007)","journal-title":"Inform. Process. Lett."},{"key":"14_CR33","unstructured":"Suomela, J.: Answer to the question \u201cIs the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?\u201d, http:\/\/cstheory.stackexchange.com\/a\/2508\/1930"},{"key":"14_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-540-30179-0_16","volume-title":"Intelligence in Communication Systems","author":"R. Ungrangsi","year":"2004","unstructured":"Ungrangsi, R., Trachtenberg, A., Starobinski, D.: An implementation of indoor location detection systems based on identifying codes. In: Aagesen, F.A., Anutariya, C., Wuwongse, V. (eds.) INTELLCOMM 2004. LNCS, vol.\u00a03283, pp. 175\u2013189. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45278-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T07:24:27Z","timestamp":1647501867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45278-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642452772","9783642452789"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45278-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}