{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:31:55Z","timestamp":1775838715995,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642330896","type":"print"},{"value":"9783642330902","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_37","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"419-430","source":"Crossref","is-referenced-by-count":27,"title":["On the Complexity of Metric Dimension"],"prefix":"10.1007","author":[{"given":"Josep","family":"D\u00edaz","sequence":"first","affiliation":[]},{"given":"Olli","family":"Pottonen","sequence":"additional","affiliation":[]},{"given":"Maria","family":"Serna","sequence":"additional","affiliation":[]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"37_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1112\/blms\/bdq096","volume":"43","author":"R.F. Bailey","year":"2011","unstructured":"Bailey, R.F., Cameron, P.J.: Base size, metric dimension and other invariants of groups and graphs. Bulletin London Math. Society\u00a043(2), 209\u2013242 (2011)","journal-title":"Bulletin London Math. Society"},{"key":"37_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, T., Erlebach, T., Hall, A., Hoffmann, M., Mihalak, M., Ram, L.: Network Discovery and Verification. IEEE J. Selected Areas in Communication\u00a024, 2168\u20132181 (2006)","journal-title":"IEEE J. Selected Areas in Communication"},{"key":"37_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. JACM\u00a041, 153\u2013180 (1994)","journal-title":"JACM"},{"key":"37_CR4","first-page":"116","volume":"36","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Classes of Graphs with Bounded Treewidth. Bulletin of the EATCS\u00a036, 116\u2013125 (1988)","journal-title":"Bulletin of the EATCS"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 194\u2013242. Elsevier Science (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"37_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.A., Oellemann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discrete Applied Math.\u00a0105, 99\u2013113 (2000)","journal-title":"Discrete Applied Math."},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The Complexity of Multiterminal Cuts. SIAM J. Computing\u00a023, 864\u2013894 (1994)","journal-title":"SIAM J. Computing"},{"key":"37_CR8","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: SODA 2005, pp. 590\u2013601 (2005)"},{"key":"37_CR9","unstructured":"Diestel, R.: Graph Theory. Springer (2000)"},{"key":"37_CR10","unstructured":"Epstein, L., Levin, A., Woeginger, G.J.: The (weighted) metric dimension of graphs: hard and easy cases. In: Proc. WG 2012 (to appear, 2012)"},{"key":"37_CR11","unstructured":"Erickson, L.H., Carraher, J., Choi, I., Delcourt, M., West, D.B.: Locating a robber on a graph via distance queries (preprint)"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica\u00a027, 275\u2013291 (2000)","journal-title":"Algorithmica"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: SODA 2011, pp. 748\u2013759 (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"37_CR14","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979)"},{"key":"37_CR15","first-page":"191","volume":"2","author":"F. Harary","year":"1976","unstructured":"Harary, F., Melter, R.A.: The metric dimension of a graph. Ars Combinatoria\u00a02, 191\u2013195 (1976)","journal-title":"Ars Combinatoria"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Hauptmann, M., Schmied, R., Viehmann, C.: On approximation complexity of metric dimension problem. In: J. Discrete Algorithms (2011) (in press)","DOI":"10.1007\/978-3-642-19222-7_15"},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. JACM\u00a021, 549\u2013568 (1974)","journal-title":"JACM"},{"key":"37_CR18","unstructured":"Johnson, D.S.: Personal communication"},{"key":"37_CR19","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0166-218X(95)00106-2","volume":"70","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in Graphs. Discrete Applied Math.\u00a070, 217\u2013229 (1996)","journal-title":"Discrete Applied Math."},{"key":"37_CR20","unstructured":"Lokshtanov, D.: Metric Dimension. In: Demaine, E.D., Hajiaghayi, M.T., Marx, D. (eds.) Open Problems from Dagstuhl Seminar 09511 (2009), \n                  \n                    http:\/\/erikdemaine.org\/papers\/DagstuhlFPT2009Open\/paper.pdf"},{"key":"37_CR21","first-page":"549","volume":"14","author":"P. Slater","year":"1975","unstructured":"Slater, P.: Leaves of trees. Congressus Numerantium\u00a014, 549\u2013559 (1975)","journal-title":"Congressus Numerantium"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T02:16:39Z","timestamp":1557195399000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}