{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:40:32Z","timestamp":1759848032874},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642192210"},{"type":"electronic","value":"9783642192227"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_15","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T04:03:12Z","timestamp":1300075392000},"page":"136-139","source":"Crossref","is-referenced-by-count":3,"title":["On Approximation Complexity of Metric Dimension Problem"],"prefix":"10.1007","author":[{"given":"Mathias","family":"Hauptmann","sequence":"first","affiliation":[]},{"given":"Richard","family":"Schmied","sequence":"additional","affiliation":[]},{"given":"Claus","family":"Viehmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","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.: Network Discovery and Verification. IEEE J. on Selected Areas in Communications\u00a024, 2168\u20132181 (2006)","journal-title":"IEEE J. on Selected Areas in Communications"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.jcss.2005.02.001","volume":"71","author":"P. Berman","year":"2005","unstructured":"Berman, P., DasGupta, B., Kao, M.: Tight approximability results for test set problems in bioinformatics. J. Comput. Syst. Sci.\u00a071, 145\u2013162 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/050641867","volume":"21","author":"J. C\u00e1ceres","year":"2007","unstructured":"C\u00e1ceres, J., Hernando, C., Mora, M., Pelayo, I., Puertas, M., Seara, C., Wood, D.: On the Metric Dimension of Cartesian Products of Graphs. SIAM J. Disc. Math.\u00a021, 423\u2013441 (2007)","journal-title":"SIAM J. Disc. Math."},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.endm.2009.11.004","volume":"35","author":"J. C\u00e1ceres","year":"2009","unstructured":"C\u00e1ceres, J., Hernando, C., Mora, M., Pelayo, I., Puertas, M.: On the Metric Dimension of Infinite Graphs. Electr. Notes in Disc. Math.\u00a035, 15\u201320 (2009)","journal-title":"Electr. Notes in Disc. Math."},{"key":"15_CR5","first-page":"349","volume":"88","author":"G. Chappell","year":"2008","unstructured":"Chappell, G., Gimbel, J., Hartman, C.: Bounds on the metric and partition dimensions of a graph. Ars Combinatoria\u00a088, 349\u2013366 (2008)","journal-title":"Ars Combinatoria"},{"key":"15_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.\u00a0105, 99\u2013133 (2000)","journal-title":"Disc. Appl. Math."},{"key":"15_CR7","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. Inf. Comput.\u00a0206, 1264\u20131275 (2008)","journal-title":"Inf. Comput."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02579188","volume":"3","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Mastermind. Combinatorica\u00a03, 325\u2013329 (1983)","journal-title":"Combinatorica"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.disc.2005.09.015","volume":"306","author":"M. Fehr","year":"2006","unstructured":"Fehr, M., Gosselin, S., Oellermann, O.: The metric dimension of Cayley digraphs. Disc. Math.\u00a0306, 31\u201341 (2006)","journal-title":"Disc. Math."},{"key":"15_CR10","volume-title":"Computers and Intractability: A Guide to the Theory on NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory on NP-Completeness. Freeman, New York (1979)"},{"key":"15_CR11","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. Halld\u00f3rsson","year":"2001","unstructured":"Halld\u00f3rsson, B., Halld\u00f3rsson, 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":"15_CR12","first-page":"191","volume":"2","author":"F. Harary","year":"1976","unstructured":"Harary, F., Melter, R.: On the metric dimension of a graph. Ars Combinatoria\u00a02, 191\u2013195 (1976)","journal-title":"Ars Combinatoria"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.endm.2007.07.058","volume":"29","author":"C. Hernando","year":"2007","unstructured":"Hernando, C., Mora, M., Pelayo, I., Seara, C., Wood, D.: Extremal Graph Theory for Metric Dimension and Diameter. Electr. Notes in Disc. Math.\u00a029, 339\u2013343 (2007)","journal-title":"Electr. Notes in Disc. Math."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schudy, W.: Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. In: Proc. 41st ACM STOC, pp. 313\u2013322 (2009)","DOI":"10.1145\/1536414.1536458"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Zelikovsky, A.: Approximating Dense Cases of Covering Problems. In: Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location 1997, pp. 169\u2013178 (1997); also published in ECCC TR97-004","DOI":"10.1090\/dimacs\/040\/11"},{"key":"15_CR16","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. Disc. Appl. Math.\u00a070, 217\u2013229 (1996)","journal-title":"Disc. Appl. Math."},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1287\/moor.1030.0070","volume":"29","author":"A. Seb\u00f6","year":"2004","unstructured":"Seb\u00f6, A., Tannier, E.: On Metric Generators of Graphs. Math. Oper. Res.\u00a029, 383\u2013393 (2004)","journal-title":"Math. Oper. Res."},{"key":"15_CR18","first-page":"549","volume-title":"Southeastern Conf. on Combin., Graph Theory, and Comp., Congressus Numerantium","author":"P. Slater","year":"1975","unstructured":"Slater, P.: Leaves of trees. In: Hoffman, et al. (eds.) Southeastern Conf. on Combin., Graph Theory, and Comp., Congressus Numerantium, vol.\u00a014, pp. 549\u2013559. Utilitas Mathematica, Winnipeg (1975)"},{"key":"15_CR19","first-page":"445","volume":"22","author":"P. Slater","year":"1988","unstructured":"Slater, P.: Dominating and reference sets in graphs. J. Math. Phys. Sci.\u00a022, 445\u2013455 (1988)","journal-title":"J. Math. Phys. Sci."},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.2307\/2312835","volume":"70","author":"H. Shapiro","year":"1963","unstructured":"Shapiro, H., S\u00f6derberg, S.: A combinatory detection problem. Amer. Math. Monthly\u00a070, 1066\u20131070 (1963)","journal-title":"Amer. Math. Monthly"},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"5026","DOI":"10.1016\/j.disc.2007.08.089","volume":"308","author":"I. Tomescu","year":"2008","unstructured":"Tomescu, I.: Discrepancies between metric dimension and partition dimension of a connected graph. Disc. Math.\u00a0308, 5026\u20135031 (2008)","journal-title":"Disc. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T06:36:42Z","timestamp":1558420602000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}