{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T18:06:46Z","timestamp":1776881206517,"version":"3.51.2"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T00:00:00Z","timestamp":1571443200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T00:00:00Z","timestamp":1571443200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MTR\/2018\/000017"],"award-info":[{"award-number":["MTR\/2018\/000017"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006565","name":"University of Johannesburg","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006565","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s10878-019-00457-3","type":"journal-article","created":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T15:39:25Z","timestamp":1571499565000},"page":"90-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Algorithmic results on double Roman domination in graphs"],"prefix":"10.1007","volume":"39","author":[{"given":"S.","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Henning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Pradhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,19]]},"reference":[{"key":"457_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2017.06.014","volume":"232","author":"HA Ahangar","year":"2017","unstructured":"Ahangar HA, Chellali M, Sheikholeslami SM (2017) On the double Roman domination in graphs. Discrete Appl Math 232:1\u20137","journal-title":"Discrete Appl Math"},{"key":"457_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2018.09.009","volume":"257","author":"HA Ahangar","year":"2019","unstructured":"Ahangar HA, Chellali M, Sheikholeslami SM (2019) Signed double Roman domination in graphs. Discrete Appl Math 257:1\u201311","journal-title":"Discrete Appl Math"},{"key":"457_CR3","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s10878-012-9500-0","volume":"27","author":"HA Ahangar","year":"2014","unstructured":"Ahangar HA, Henning MA, L\u00f6wenstein C, Zhao Y, Samodivkin V (2014) Signed Roman domination in graphs. J Comb Optim 27:241\u2013255","journal-title":"J Comb Optim"},{"key":"457_CR4","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Boston"},{"key":"457_CR5","doi-asserted-by":"crossref","unstructured":"Alimonti P, Kann V (1997) Hardness of approximating problems on cubic graphs. In: Proceedings of 3rd Italian conference on algorithms and complexity, Rome, Lect Notes in Comput Sc 1203:288\u2013298","DOI":"10.1007\/3-540-62592-5_80"},{"issue":"1","key":"457_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s10878-018-0286-6","volume":"36","author":"J Amjadi","year":"2018","unstructured":"Amjadi J, Nazari-Moghaddam S, Sheikholeslami SM, Volkmann L (2018) An upper bound on the double Roman domination number. J Comb Optim 36(1):81\u201389","journal-title":"J Comb Optim"},{"key":"457_CR7","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.dam.2018.03.026","volume":"244","author":"V Anu","year":"2018","unstructured":"Anu V, Lakshmanan SA (2018) Double Roman domination number. Discrete Appl Math 244:198\u2013204","journal-title":"Discrete Appl Math"},{"key":"457_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation : combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation : combinatorial optimization problems and their approximability properties. Springer, Berlin"},{"key":"457_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.dam.2016.03.017","volume":"211","author":"RA Beeler","year":"2016","unstructured":"Beeler RA, Haynes TW, Hedetniemi ST (2016) Double Roman domination. Discrete Appl Math 211:23\u201329","journal-title":"Discrete Appl Math"},{"key":"457_CR10","first-page":"205","volume":"9","author":"KS Booth","year":"1974","unstructured":"Booth KS, Johnson JH (1974) Dominating sets in chordal graphs. SIAM J Comput 9:205\u2013212","journal-title":"SIAM J Comput"},{"key":"457_CR11","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.dam.2015.11.013","volume":"204","author":"M Chellali","year":"2016","unstructured":"Chellali M, Haynes TW, Hedetniemi ST, MacRae A (2016) Roman $$\\{2\\}$$-domination. Discrete Appl Math 204:22\u201328","journal-title":"Discrete Appl Math"},{"key":"457_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal V (1979) A greedy heuristic for the set covering problem. Math Oper Res 4:233\u2013235","journal-title":"Math Oper Res"},{"key":"457_CR13","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne EJ, Dreyer PA, Hedetniemi SM, Hedetniemi ST (2004) Roman domination in graphs. Discrete Math 278:11\u201322","journal-title":"Discrete Math"},{"key":"457_CR14","doi-asserted-by":"crossref","unstructured":"Dinur I, Steurer D (2014) Analytical approach to parallel repetition. In: Proceedings of symposium on theory of computing, STOC, 2014, pp 624\u2013633","DOI":"10.1145\/2591796.2591884"},{"key":"457_CR15","volume-title":"Domination in graphs: advanced topics","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998a) Domination in graphs: advanced topics. Marcel Dekker Inc, New York"},{"key":"457_CR16","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998b) Fundamentals of domination in graphs. Marcel Dekker Inc, New York"},{"key":"457_CR17","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0012-365X(02)00811-7","volume":"266","author":"MA Henning","year":"2003","unstructured":"Henning MA, Hedetniemi ST (2003) Defending the Roman empire-a new strategy. Discrete Math 266:239\u2013251","journal-title":"Discrete Math"},{"key":"457_CR18","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.dam.2018.12.033","volume":"259","author":"MA Henning","year":"2019","unstructured":"Henning MA, Rad N (2019) A characterization of double Roman trees. Discrete Appl Math 259:100\u2013111","journal-title":"Discrete Appl Math"},{"key":"457_CR19","unstructured":"Jamison RE, Laskar RC (1982) Elimination orderings of chordal graphs. Combinatorics and Applications, Calcutta, 1982. ISI, Calcutta, pp 192\u2013200"},{"key":"457_CR20","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0166-218X(93)90178-Q","volume":"42","author":"JM Keil","year":"1993","unstructured":"Keil JM (1993) The complexity of domination problems in circle graphs. Discrete Appl Math 42:51\u201363","journal-title":"Discrete Appl Math"},{"key":"457_CR21","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H M\u00fcller","year":"1987","unstructured":"M\u00fcller H, Brandst\u00e4dt A (1987) The NP-completeness of STEINER TREE and DOMINATING SET for chordal bipartite graphs. Theoret Comput Sci 53:257\u2013265","journal-title":"Theoret Comput Sci"},{"key":"457_CR22","unstructured":"Mojdeh DA, Parsian A, Masoumi I (2017) Bounds on double Roman domination number of graphs. In: Proceedings of the 2nd international conference on combinatorics, cryptography and computation (I4C2017)"},{"key":"457_CR23","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"BS Panda","year":"2003","unstructured":"Panda BS, Das SK (2003) A linear time recognition algorithm for proper interval graphs. Inf Process Lett 87:153\u2013161","journal-title":"Inf Process Lett"},{"issue":"1","key":"457_CR24","doi-asserted-by":"publisher","first-page":"41","DOI":"10.7151\/dmgt.2069","volume":"39","author":"NJ Rad","year":"2019","unstructured":"Rad NJ, Rahbani H (2019) Some progress on double Roman domination in graphs. Discuss Math Graph Theory 39(1):41\u201353","journal-title":"Discuss Math Graph Theory"},{"key":"457_CR25","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1080\/00029890.2000.12005243","volume":"107","author":"CS ReVelle","year":"2000","unstructured":"ReVelle CS, Rosing KE (2000) Defendens imperium romanum: a classical problem in military strategy. Am Math Monthly 107:585\u2013594","journal-title":"Am Math Monthly"},{"issue":"1","key":"457_CR26","first-page":"31","volume":"22","author":"Z Shao","year":"2019","unstructured":"Shao Z, Sheikholeslami SM, Nazari-Moghaddam S, Wang S (2019) Global double Roman domination in graphs. J Discrete Math Sci Crytogr 22(1):31\u201344","journal-title":"J Discrete Math Sci Crytogr"},{"key":"457_CR27","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","volume":"281","author":"I Stewart","year":"1999","unstructured":"Stewart I (1999) Defend the Roman empire!. Sci Am 281:136\u2013139","journal-title":"Sci Am"},{"issue":"1","key":"457_CR28","first-page":"71","volume":"3","author":"L Volkmann","year":"2018","unstructured":"Volkmann L (2018) Double Roman domination and domatic numbers of graphs. Commun Comb Optim 3(1):71\u201377","journal-title":"Commun Comb Optim"},{"key":"457_CR29","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(94)00138-4","volume":"66","author":"CC Yen","year":"1996","unstructured":"Yen CC, Lee RCT (1996) The weighted perfect domination problem and its variants. Discrete Appl Math 66:147\u2013160","journal-title":"Discrete Appl Math"},{"key":"457_CR30","first-page":"669","volume":"338","author":"J Yue","year":"2018","unstructured":"Yue J, Wei M, Li M, Liu G (2018) On the double Roman domination of graphs. Appl Math Comput 338:669\u2013675","journal-title":"Appl Math Comput"},{"key":"457_CR31","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.ipl.2018.01.004","volume":"134","author":"X Zhang","year":"2018","unstructured":"Zhang X, Li Z, Jiang H, Shao Z (2018) Double Roman domination in trees. Inf Process Lett 134:31\u201334","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00457-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00457-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00457-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,17]],"date-time":"2020-10-17T23:25:23Z","timestamp":1602977123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00457-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,19]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["457"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00457-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,19]]},"assertion":[{"value":"19 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}