{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T12:10:21Z","timestamp":1782821421428,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662480533","type":"print"},{"value":"9783662480540","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_10","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"115-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Metric Dimension of Bounded Width Graphs"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"issue":"1\u20133","key":"10_CR1","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(97)00031-0","volume":"79","author":"HL Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Treewidth for graphs with small chordality. Discrete Appl. Math. 79(1\u20133), 45\u201361 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10_CR2","first-page":"25","volume":"7","author":"LS Chandran","year":"2005","unstructured":"Chandran, L.S., Lozin, V.V., Subramanian, C.R.: Graphs of low chordality. Discrete Math. & Theor. Comput. Sci. 7(1), 25\u201336 (2005). www.dmtcs.org\/volumes\/abstracts\/dm070103.abs.html","journal-title":"Discrete Math. & Theor. Comput. Sci."},{"issue":"1\u20133","key":"10_CR3","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., Oellermann, O.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105(1\u20133), 99\u2013113 (2000)","journal-title":"Discrete Appl. Math."},{"key":"10_CR4","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)"},{"issue":"16","key":"10_CR5","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Math. 307(16), 2008\u20132029 (2007)","journal-title":"Discrete Math."},{"key":"10_CR6","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, London (2013)"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-642-34611-8_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L Epstein","year":"2012","unstructured":"Epstein, L., Levin, A., Woeginger, G.J.: The (weighted) metric dimension of graphs: hard and easy cases. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 114\u2013125. Springer, Heidelberg (2012)"},{"key":"10_CR8","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin (2006)"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Identification, location-domination and metric dimension on interval and permutation graphs. In: Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 to appear","DOI":"10.1007\/s00453-016-0184-1"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Heidelberg (2013)"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar 18, 25\u201366 (1967)","journal-title":"Acta Math. Acad. Sci. Hungar"},{"key":"10_CR12","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 Franciso (1979)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Algorithms - ESA 2001","author":"C Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 476\u2013487. Springer, Heidelberg (2001)"},{"issue":"1","key":"10_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010)","journal-title":"Comput. Sci. Rev."},{"key":"10_CR15","first-page":"191","volume":"2","author":"F Harary","year":"1976","unstructured":"Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combinatoria 2, 191\u2013195 (1976)","journal-title":"Ars Combinatoria"},{"key":"10_CR16","doi-asserted-by":"crossref","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, pp. 266\u2013276. K.lo Alto, California, USA, 5\u20137 June 2013","DOI":"10.1109\/CCC.2013.36"},{"key":"10_CR17","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)"},{"issue":"3","key":"10_CR18","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 Appl. Math. 70(3), 217\u2013229 (1996)","journal-title":"Discrete Appl. Math."},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"7","key":"10_CR20","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1016\/j.dam.2009.10.007","volume":"158","author":"D Lokshtanov","year":"2010","unstructured":"Lokshtanov, D.: On the complexity of computing treelength. Discrete Appl. Math. 158(7), 820\u2013827 (2010)","journal-title":"Discrete Appl. Math."},{"key":"10_CR21","series-title":"Oxford Lecture Series in Mathematics and its Applications","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 Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"key":"10_CR22","unstructured":"Slater, P.J.: Leaves of trees. In: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975). pp. 549\u2013559. Congressus Numerantium, No. XIV. Utilitas Math., Winnipeg, Man (1975)"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T12:19:29Z","timestamp":1674908369000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}