{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T00:57:49Z","timestamp":1778633869966,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. Appl. Math. Comput."],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s12190-020-01345-4","type":"journal-article","created":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T08:02:37Z","timestamp":1587196957000},"page":"89-102","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Algorithmic aspects of Roman domination in graphs"],"prefix":"10.1007","volume":"64","author":[{"given":"Chakradhar","family":"Padamutham","sequence":"first","affiliation":[]},{"given":"Venkata Subba Reddy","family":"Palagiri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,18]]},"reference":[{"key":"1345_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237, 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"1345_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1345_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Math. 278, 11\u201322 (2004)","journal-title":"Discrete Math."},{"key":"1345_CR4","unstructured":"Dreyer, P.A.: Applications and variations of domination in graphs. Rutgers University, The State University of New Jersey, New Brunswick, NJ, Ph.D. Thesis (2000)"},{"key":"1345_CR5","doi-asserted-by":"publisher","first-page":"3447","DOI":"10.1016\/j.disc.2008.09.043","volume":"309","author":"O Favaron","year":"2009","unstructured":"Favaron, O., Karami, H., Khoeilar, R., Sheikholeslami, S.M.: On the Roman domination number of a graph. Discrete Math. 309, 3447\u20133451 (2009)","journal-title":"Discrete Math."},{"key":"1345_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$ln~n$$ for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"1345_CR7","volume-title":"Computers and Interactability : A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Interactability : A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"1345_CR8","volume-title":"Fundamentals of Domination in Graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. CRC Press, Boca Raton (1998)"},{"key":"1345_CR9","doi-asserted-by":"publisher","first-page":"325","DOI":"10.7151\/dmgt.1178","volume":"22","author":"M Henning","year":"2002","unstructured":"Henning, M.: A characterization of Roman trees. Discuss. Math. Graph Theory 22, 325\u2013334 (2002)","journal-title":"Discuss. Math. Graph Theory"},{"key":"1345_CR10","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0012-365X(03)00040-2","volume":"271","author":"M Henning","year":"2003","unstructured":"Henning, M.: Defending the Roman Empire from multiple attacks. Discrete Math. 271, 101\u2013115 (2003)","journal-title":"Discrete Math."},{"key":"1345_CR11","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0012-365X(02)00811-7","volume":"266","author":"MA Henning","year":"2003","unstructured":"Henning, M.A., Hedetniemi, S.T.: Defending the Roman Empire\u2014a new strategy. Discrete Math. 266, 239\u2013251 (2003)","journal-title":"Discrete Math."},{"key":"1345_CR12","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.dam.2016.08.017","volume":"218","author":"M Lin","year":"2017","unstructured":"Lin, M., Chen, C.: Counting independent sets in tree convex bipartite graphs. Discrete Appl. Math. 218, 113\u2013122 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1345_CR13","volume-title":"Introduction to Algorithms","author":"CE Leiserson","year":"2001","unstructured":"Leiserson, C.E., Rivest, R.L., Cormen, T.H., Stein, C.: Introduction to Algorithms, vol. 6. MIT Press, Cambridge (2001)"},{"key":"1345_CR14","unstructured":"Liedloff, M., Kloks, T., Liu, J., Peng, S.H.: Roman domination in some special classes of graphs. Report TR-MA-04-01 (2004)"},{"key":"1345_CR15","volume-title":"Threshold Graphs and Related Topics","author":"N Mahadev","year":"1995","unstructured":"Mahadev, N., Peled, U.: Threshold Graphs and Related Topics. Elsevier, North Holland (1995)"},{"key":"1345_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"1345_CR17","first-page":"167","volume":"19","author":"NJ Rad","year":"2019","unstructured":"Rad, N.J., Volkmann, L.: Roman domination perfect graphs. An. Stiint. Univ. Ovidius Constanta Ser. Mat. 19, 167\u2013174 (2019)","journal-title":"An. Stiint. Univ. Ovidius Constanta Ser. Mat."},{"key":"1345_CR18","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1080\/00029890.2000.12005243","volume":"107","author":"CS ReVelle","year":"2000","unstructured":"ReVelle, C.S., Rosing, K.E.: Defendens imperium romanum: a classical problem in military strategy. Am. Math. Mon. 107, 585\u2013594 (2000)","journal-title":"Am. Math. Mon."},{"key":"1345_CR19","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, 136\u2013138 (1999)","journal-title":"Sci. Am."},{"key":"1345_CR20","doi-asserted-by":"crossref","unstructured":"Uehara, R., Uno, Y.: Efficient algorithms for the longest path problem. In: International Symposium on Algorithms and Computation, pp. 871\u2013883 (2004)","DOI":"10.1007\/978-3-540-30551-4_74"},{"key":"1345_CR21","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, vol. 2. Prentice Hall, Upper Saddle River (2001)"},{"key":"1345_CR22","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node-and edge-deletion np-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 253\u2013264 (1978)","DOI":"10.1145\/800133.804355"}],"container-title":["Journal of Applied Mathematics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12190-020-01345-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12190-020-01345-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12190-020-01345-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,18]],"date-time":"2021-04-18T00:04:52Z","timestamp":1618704292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12190-020-01345-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,18]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["1345"],"URL":"https:\/\/doi.org\/10.1007\/s12190-020-01345-4","relation":{},"ISSN":["1598-5865","1865-2085"],"issn-type":[{"value":"1598-5865","type":"print"},{"value":"1865-2085","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,18]]},"assertion":[{"value":"4 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}