{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T09:47:54Z","timestamp":1767865674757,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662531730","type":"print"},{"value":"9783662531747","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_32","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"456-471","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs"],"prefix":"10.1007","author":[{"given":"Florent","family":"Foucaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reza","family":"Naserasr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aline","family":"Parreau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petru","family":"Valicov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"issue":"1","key":"32_CR1","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/0209018","volume":"9","author":"L Babai","year":"1980","unstructured":"Babai, L.: On the complexity of canonical labelling of strongly regular graphs. SIAM J. Comput. 9(1), 212\u2013216 (1980)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"32_CR2","doi-asserted-by":"publisher","first-page":"2168","DOI":"10.1109\/JSAC.2006.884015","volume":"24","author":"Z Beerliova","year":"2006","unstructured":"Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal\u00e1k, M., Ram, L.S.: Network discovery and verification. IEEE J. Sel. Area Comm. 24(12), 2168\u20132181 (2006)","journal-title":"IEEE J. Sel. Area Comm."},{"issue":"3","key":"32_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"32_CR4","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1137\/14097879X","volume":"29","author":"N Bousquet","year":"2015","unstructured":"Bousquet, N., Lagoutte, A., Li, Z., Parreau, A., Thomass\u00e9, S.: Identifying codes in hereditary classes of graphs and VC-dimension. SIAM J. Discrete Math. 29(4), 2047\u20132064 (2015)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"32_CR5","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. 290(3), 2109\u20132120 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"32_CR6","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0166-218X(00)00198-0","volume":"105","author":"G Chartrand","year":"2000","unstructured":"Chartrand, G., Eroh, L., Johnson, M., Oellermann, O.: Resolvability in graphs and the metric dimension of a graph. Disc. Appl. Math. 105(1\u20133), 99\u2013113 (2000)","journal-title":"Disc. Appl. Math."},{"key":"32_CR7","first-page":"135","volume":"56","author":"C Colbourn","year":"1987","unstructured":"Colbourn, C., Slater, P.J., Stewart, L.K.: Locating-dominating sets in series-parallel networks. Congr. Numer. 56, 135\u2013162 (1987)","journal-title":"Congr. Numer."},{"issue":"1","key":"32_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"32_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-642-33090-2_37","volume-title":"Algorithms \u2013 ESA 2012","author":"J D\u00edaz","year":"2012","unstructured":"D\u00edaz, J., Pottonen, O., Serna, M., van Leeuwen, E.J.: On the complexity of metric dimension. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 419\u2013430. Springer, Heidelberg (2012)"},{"key":"32_CR10","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Heidelberg (2013)"},{"issue":"4","key":"32_CR11","doi-asserted-by":"publisher","first-page":"1130","DOI":"10.1007\/s00453-014-9896-2","volume":"72","author":"L Epstein","year":"2015","unstructured":"Epstein, L., Levin, A., Woeginger, G.J.: The (weighted) metric dimension of graphs: hard and easy cases. Algorithmica 72(4), 1130\u20131171 (2015)","journal-title":"Algorithmica"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.ipl.2015.04.006","volume":"115","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Heggernes, P., van\u2019t Hof, P., Meister, D., Saei, R.: Computing the metric dimension for chain graphs. Inform. Process. Lett. 115, 671\u2013676 (2015)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"32_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(95)00062-V","volume":"63","author":"C Flotow","year":"1995","unstructured":"Flotow, C.: On powers of m-trapezoid graphs. Disc. Appl. Math. 63(2), 187\u2013192 (1995)","journal-title":"Disc. Appl. Math."},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.jda.2014.08.004","volume":"31","author":"F Foucaud","year":"2015","unstructured":"Foucaud, F.: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. J. Discrete Alg. 31, 48\u201368 (2015)","journal-title":"J. Discrete Alg."},{"issue":"4","key":"32_CR15","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. 73(4), 425\u2013448 (2013)","journal-title":"J. Graph Theor."},{"key":"32_CR16","unstructured":"Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., Valico, P.: Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, to appear (2016). \n                      arXiv:1405.2424"},{"key":"32_CR17","unstructured":"Foucaud, F., Naserasr, R., Parreau, A., Valicov, P.: On powers of interval graphs and their orders. \n                      arXiv:1505.03459"},{"key":"32_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"key":"32_CR19","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier, Amsterdam (2004)"},{"issue":"1","key":"32_CR20","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. Algorithmic Oper. Res. 3(1), 43\u201350 (2008)","journal-title":"Algorithmic Oper. Res."},{"key":"32_CR21","first-page":"191","volume":"2","author":"F Harary","year":"1976","unstructured":"Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191\u2013195 (1976)","journal-title":"Ars Comb."},{"key":"32_CR22","unstructured":"Hartung, S.: Exploring parameter spaces in coping with computational intractability. Ph.D. Thesis, TU Berlin, Germany (2014)"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"Hartung, S., Nichterlein, A.: On the parameterized and approximation hardness of metric dimension. In: Proceedings of the CCC 2013, pp. 266\u2013276 (2013)","DOI":"10.1109\/CCC.2013.36"},{"key":"32_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-36092-3_10","volume-title":"Algorithms for Sensor Systems","author":"S Hoffmann","year":"2013","unstructured":"Hoffmann, S., Wanke, E.: Metric Dimension for gabriel unit disk graphs Is NP-complete. In: Bar-Noy, A., Halld\u00f3rsson, M.M. (eds.) ALGOSENSORS 2012. LNCS, vol. 7718, pp. 90\u201392. Springer, Heidelberg (2013)"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20132","key":"32_CR26","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1002\/rsa.20049","volume":"26","author":"JH Kim","year":"2005","unstructured":"Kim, J.H., Pikhurko, O., Spencer, J., Verbitsky, O.: How complex are random graphs in first order logic? Random Struct. Alg. 26(1\u20132), 119\u2013145 (2005)","journal-title":"Random Struct. Alg."},{"key":"32_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994)"},{"issue":"1","key":"32_CR28","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.jda.2006.09.002","volume":"6","author":"P Manuel","year":"2008","unstructured":"Manuel, P., Rajan, B., Rajasingh, I., Chris-Monica, M.: On minimum metric dimension of honeycomb networks. J. Discrete Alg. 6(1), 20\u201327 (2008)","journal-title":"J. Discrete Alg."},{"issue":"6","key":"32_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. 18(6), 925\u2013952 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"32_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"32_CR31","first-page":"235","volume":"59","author":"A Raychaudhuri","year":"1987","unstructured":"Raychaudhuri, A.: On powers of interval graphs and unit interval graphs. Congr. Numer. 59, 235\u2013242 (1987)","journal-title":"Congr. Numer."},{"key":"32_CR32","first-page":"549","volume":"14","author":"PJ Slater","year":"1975","unstructured":"Slater, P.J.: Leaves of trees. Congr. Numer. 14, 549\u2013559 (1975)","journal-title":"Congr. Numer."},{"issue":"1","key":"32_CR33","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230170105","volume":"17","author":"PJ Slater","year":"1987","unstructured":"Slater, P.J.: Domination and location in acyclic graphs. Networks 17(1), 55\u201364 (1987)","journal-title":"Networks"},{"issue":"4","key":"32_CR34","first-page":"445","volume":"22","author":"PJ Slater","year":"1988","unstructured":"Slater, P.J.: Dominating and reference sets in a graph. J. Math. Phys. Sci. 22(4), 445\u2013455 (1988)","journal-title":"J. Math. Phys. Sci."},{"issue":"1","key":"32_CR35","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. 103(1), 28\u201333 (2007)","journal-title":"Inform. Process. Lett."},{"key":"32_CR36","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. 3283, pp. 175\u2013189. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:11:53Z","timestamp":1558314713000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}