{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:45:48Z","timestamp":1770993948023,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U20A2068"],"award-info":[{"award-number":["U20A2068"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771013"],"award-info":[{"award-number":["11771013"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11901533"],"award-info":[{"award-number":["11901533"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LD19A010001"],"award-info":[{"award-number":["LD19A010001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s11590-022-01862-0","type":"journal-article","created":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T20:04:51Z","timestamp":1648757091000},"page":"2261-2276","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Nearly tight approximation algorithm for (connected) Roman dominating set"],"prefix":"10.1007","volume":"16","author":[{"given":"Ke","family":"Li","sequence":"first","affiliation":[]},{"given":"Yingli","family":"Ran","sequence":"additional","affiliation":[]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,31]]},"reference":[{"issue":"1","key":"1862_CR1","first-page":"71","volume":"6","author":"K Antoaneta","year":"2015","unstructured":"Antoaneta, K., Ivona, P.: Roman domination number on cardinal product of paths and cycles. Kragujev. J. Math. 6(1), 71\u201378 (2015)","journal-title":"Kragujev. J. Math."},{"key":"1862_CR2","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1137\/070699688","volume":"23","author":"EW Chambers","year":"2010","unstructured":"Chambers, E.W., Kinnersley, B., Prince, N., West, D.B.: Extremal problems for roman domination. SIAM J. Discrete Math. 23, 1575\u20131586 (2010)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"1862_CR3","first-page":"11","volume":"278","author":"EJ Cockayne","year":"2000","unstructured":"Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Math. 278(1\u20133), 11\u201322 (2000)","journal-title":"Discrete Math."},{"key":"1862_CR4","first-page":"19","volume":"67","author":"EJ Cockayne","year":"2005","unstructured":"Cockayne, E.J., Grobler, P.J.P., Gr\u00fcndlingh, W.R., Munganga, J., van Vuuren, J.H.: Protection of a graph. Util. Math. 67, 19\u201332 (2005)","journal-title":"Util. Math."},{"key":"1862_CR5","unstructured":"Dreyer, P.A.: Applications and variations of domination in graphs. Ph.D. thesis, Rutgers University, New Jersey (2000)"},{"key":"1862_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1701-9","volume-title":"Design and Analysis of Approximation Algorithms","author":"DZ Du","year":"2012","unstructured":"Du, D.Z., Ko, K.I., Hu, X.: Design and Analysis of Approximation Algorithms. Springer, Berlin (2012)"},{"issue":"6","key":"1862_CR7","doi-asserted-by":"publisher","first-page":"1528","DOI":"10.1016\/j.disc.2008.03.006","volume":"309","author":"XL Fu","year":"2009","unstructured":"Fu, X.L., Yang, Y.S., Jiang, B.Q.: Roman domination in regular graphs. Discrete Math. 309(6), 1528\u20131537 (2009)","journal-title":"Discrete Math."},{"key":"1862_CR8","doi-asserted-by":"crossref","unstructured":"Lideloff, M., Kloks, T., Liu, J., Peng, S.L.: Roman domination over some graph classes. In: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 3787, pp. 103\u2013114. Springer, Berlin (2005)","DOI":"10.1007\/11604686_10"},{"issue":"3","key":"1862_CR9","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/s10878-012-9482-y","volume":"26","author":"CH Liu","year":"2013","unstructured":"Liu, C.H., Chang, G.J.: Roman domination on strongly chordal graphs. J. Comb. Optim. 26(3), 608\u2013619 (2013)","journal-title":"J. Comb. Optim."},{"key":"1862_CR10","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s12190-020-01433-5","volume":"66","author":"H Naresh Kumar","year":"2021","unstructured":"Naresh Kumar, H., Pradhan, D., Venkatakrishnan, Y.B.: Double vertex-edge domination in graphs: complexity and algorithms. J. Appl. Math. Comput. 66, 245\u2013262 (2021)","journal-title":"J. Appl. Math. Comput."},{"issue":"1\u20132","key":"1862_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s12190-020-01345-4","volume":"64","author":"C Padamutham","year":"2020","unstructured":"Padamutham, C., Palagiri, V.: Algorithmic aspects of Roman domination in graphs. J. Appl. Math. Comput. 64(1\u20132), 89\u2013102 (2020)","journal-title":"J. Appl. Math. Comput."},{"key":"1862_CR12","doi-asserted-by":"crossref","unstructured":"Pagourtzis, A., Penna, P., Schlude, K., Steinhofel, K., Taylor, D., Widmayer, P.: Server placements, Roman domination and other dominating set variants. In: Proceedings of Second International Conference on Theoretical Computer Science, pp. 280\u2013291 (2002)","DOI":"10.1007\/978-0-387-35608-2_24"},{"key":"1862_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.dam.2019.05.002","volume":"267","author":"J Raczek","year":"2019","unstructured":"Raczek, J., Cyman, J.: Weakly connected Roman domination in graphs. Discrete Appl. Math. 267, 151\u2013159 (2019)","journal-title":"Discrete Appl. Math."},{"issue":"01","key":"1862_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1142\/S1793830910000504","volume":"2","author":"W Shang","year":"2010","unstructured":"Shang, W., Wang, X., Hu, X.: Roman domination and its variants in unit disk graphs. Discrete Math. Algorithms Appl. 2(01), 99\u2013105 (2010)","journal-title":"Discrete Math. Algorithms Appl."},{"issue":"6","key":"1862_CR15","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","volume":"281","author":"I Stewart","year":"1999","unstructured":"Stewart, I.: Defend the Roman empire! Sci. Am. 281(6), 136\u2013138 (1999)","journal-title":"Sci. Am."},{"issue":"13\u201314","key":"1862_CR16","doi-asserted-by":"publisher","first-page":"2030","DOI":"10.1016\/j.dam.2012.04.008","volume":"160","author":"TK \u0160umenjak","year":"2012","unstructured":"\u0160umenjak, T.K., Pavli\u010d, P., Tepeh, A.: On the Roman domination in the lexicographic product of graphs. Discrete Appl. Math. 160(13\u201314), 2030\u20132036 (2012)","journal-title":"Discrete Appl. Math."},{"key":"1862_CR17","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/s10878-019-00459-1","volume":"39","author":"L Wang","year":"2020","unstructured":"Wang, L., Shi, Y., Zhang, Z., Zhang, Z.-B., Zhang, X.: Approximation algorithm for a generalized Roman domination problem in unit ball graphs. J. Comb. Optim. 39, 138\u2013148 (2020)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"1862_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01862-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01862-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01862-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:58:36Z","timestamp":1665061116000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01862-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":18,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1862"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01862-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,31]]},"assertion":[{"value":"5 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}