{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T10:19:33Z","timestamp":1770891573685,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T00:00:00Z","timestamp":1658102400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T00:00:00Z","timestamp":1658102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00453-022-01005-y","type":"journal-article","created":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T06:02:35Z","timestamp":1658124155000},"page":"3110-3155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Hardness of Metric Dimension in Graphs of Constant Treewidth"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8079-6405","authenticated-orcid":false,"given":"Shaohua","family":"Li","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,18]]},"reference":[{"issue":"2","key":"1005_CR1","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1137\/16M1057383","volume":"31","author":"R Belmonte","year":"2017","unstructured":"Belmonte, R., Fomin, F.V., Golovach, P.A., Ramanujan, M.S.: Metric dimension of bounded tree-length graphs. SIAM J. Discret. Math. 31(2), 1217\u20131243 (2017). https:\/\/doi.org\/10.1137\/16M1057383","journal-title":"SIAM J. Discret. Math."},{"key":"1005_CR2","doi-asserted-by":"publisher","unstructured":"Bonnet, E., Purohit, N.: Metric dimension parameterized by treewidth. In Bart M.\u00a0P. Jansen and Jan\u00a0Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 5:1\u20135:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019) https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.5","DOI":"10.4230\/LIPIcs.IPEC.2019.5"},{"issue":"1","key":"1005_CR3","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jcss.2016.06.006","volume":"83","author":"J D\u00edaz","year":"2017","unstructured":"D\u00edaz, J., Pottonen, O., Serna, M.J., van Leeuwen, E.J.: Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci. 83(1), 132\u2013158 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2016.06.006","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1005_CR4","doi-asserted-by":"publisher","first-page":"313","DOI":"10.7155\/jgaa.00360","volume":"19","author":"D Eppstein","year":"2015","unstructured":"Eppstein, D.: Metric dimension parameterized by max leaf number. J. Graph Algorithms Appl. 19(1), 313\u2013323 (2015). https:\/\/doi.org\/10.7155\/jgaa.00360","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"1005_CR5","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). https:\/\/doi.org\/10.1007\/s00453-014-9896-2","journal-title":"Algorithmica"},{"issue":"9","key":"1005_CR6","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. Inf. Process. Lett. 115(9), 671\u2013676 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2015.04.006","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1005_CR7","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1007\/s00453-016-0184-1","volume":"78","author":"F Foucaud","year":"2017","unstructured":"Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Identification, location-domination and metric dimension on interval and permutation graphs . ii. algorithms and complexity. Algorithmica 78(3), 914\u2013944 (2017)","journal-title":"Algorithmica"},{"issue":"1","key":"1005_CR8","first-page":"191","volume":"2","author":"F Harary","year":"1976","unstructured":"Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2(1), 191\u2013195 (1976)","journal-title":"Ars Combin."},{"key":"1005_CR9","doi-asserted-by":"publisher","unstructured":"Hartung, S., Nichterlein, A.: On the parameterized and approximation hardness of metric dimension. In: Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 266\u2013276. IEEE Computer Society, (2013) https:\/\/doi.org\/10.1109\/CCC.2013.36","DOI":"10.1109\/CCC.2013.36"},{"key":"1005_CR10","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations, pages 85\u2013103. Springer, (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"1005_CR11","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. Discret. Appl. Math. 70(3), 217\u2013229 (1996). https:\/\/doi.org\/10.1016\/0166-218X(95)00106-2","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1005_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"LM Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and seatching. Discret. Math. 55(2), 181\u2013184 (1985)","journal-title":"Discret. Math."},{"issue":"37","key":"1005_CR13","first-page":"549","volume":"14","author":"PJ Slater","year":"1975","unstructured":"Slater, P.J.: Leaves of trees. Congr. Numer. 14(37), 549\u2013559 (1975)","journal-title":"Congr. Numer."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01005-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01005-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01005-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,25]],"date-time":"2022-10-25T12:25:33Z","timestamp":1666700733000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01005-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,18]]},"references-count":13,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1005"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01005-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,18]]},"assertion":[{"value":"23 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors of this paper, Shaohua Li and Marcin Pilipczuk, certify that there is no actual or potential conflict of interest in relation to this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}