{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T06:45:23Z","timestamp":1768977923888,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T00:00:00Z","timestamp":1693785600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T00:00:00Z","timestamp":1693785600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"SERB, India","award":["MTR\/2018\/000017"],"award-info":[{"award-number":["MTR\/2018\/000017"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101039913"],"award-info":[{"award-number":["101039913"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00453-023-01171-7","type":"journal-article","created":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T19:02:58Z","timestamp":1693854178000},"page":"3889-3927","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Unique Response Roman Domination: Complexity and Algorithms"],"prefix":"10.1007","volume":"85","author":[{"given":"Sumanta","family":"Banerjee","sequence":"first","affiliation":[]},{"given":"Juhi","family":"Chaudhary","sequence":"additional","affiliation":[]},{"given":"Dinabandhu","family":"Pradhan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,4]]},"reference":[{"key":"1171_CR1","doi-asserted-by":"crossref","first-page":"2547","DOI":"10.1080\/00207160.2017.1301437","volume":"94","author":"HA Ahangar","year":"2017","unstructured":"Ahangar, H.A., Chellali, M., Samodivkin, V.: Outer independent Roman dominating functions in graphs. Int. J. Comput. Math. 94, 2547\u20132557 (2017)","journal-title":"Int. J. Comput. Math."},{"key":"1171_CR2","volume":"364","author":"HA Ahangar","year":"2020","unstructured":"Ahangar, H.A., Chellali, M., Sheikholeslami, S.M.: Outer independent double Roman domination. Appl. Math. Comput. 364, 124617 (2020)","journal-title":"Appl. Math. Comput."},{"key":"1171_CR3","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/s10878-012-9500-0","volume":"27","author":"HA Ahangar","year":"2014","unstructured":"Ahangar, H.A., Henning, M.A., L\u00f6wenstein, C., Zhao, Y., Samodivkin, V.: Signed Roman domination in graphs. J. Comb. Optim. 27, 241\u2013255 (2014)","journal-title":"J. Comb. Optim."},{"key":"1171_CR4","doi-asserted-by":"crossref","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., Protasi, M., Spaccamela, A.M., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, New York (1999)"},{"key":"1171_CR5","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"HJ Bandelt","year":"1986","unstructured":"Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Combin. Theory Ser. B 41, 182\u2013208 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1171_CR6","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/s10878-019-00457-3","volume":"39","author":"S Banerjee","year":"2020","unstructured":"Banerjee, S., Henning, M.A., Pradhan, D.: Algorithmic results on double Roman domination in graphs. J. Comb. Optim. 39, 90\u2013114 (2020)","journal-title":"J. Comb. Optim."},{"key":"1171_CR7","volume":"391","author":"S Banerjee","year":"2021","unstructured":"Banerjee, S., Henning, M.A., Pradhan, D.: Perfect Italian domination in cographs. Appl. Math. Comput. 391, 125703 (2021)","journal-title":"Appl. Math. Comput."},{"key":"1171_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2019.08.017","volume":"796","author":"S Banerjee","year":"2019","unstructured":"Banerjee, S., Keil, J.M., Pradhan, D.: Perfect Roman domination in graphs. Theor. Comput. Sci. 796, 1\u201321 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"1171_CR9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.dam.2016.03.017","volume":"211","author":"RA Beeler","year":"2016","unstructured":"Beeler, R.A., Haynes, T.W., Hedetniemi, S.T.: Double Roman domination. Discrete Appl. Math. 211, 23\u201329 (2016)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR10","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"AA Bertossi","year":"1984","unstructured":"Bertossi, A.A.: Dominating sets for split and bipartite graphs. Inf. Process. Lett. 19, 37\u201340 (1984)","journal-title":"Inf. Process. Lett."},{"key":"1171_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V.D., Dargan, F.F.: The algorithmic use of hypertree structure and maximum neighborhood orderings. Discrete Appl. Math. 82, 43\u201377 (1998)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR12","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., L\u00ea, V.B., Spinrad, J.P.: Graph classes: a survey, SIAM Monogr. Dis. Math. Appl. (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"1171_CR13","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"6","author":"MS Chang","year":"1998","unstructured":"Chang, M.S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 6, 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"key":"1171_CR14","doi-asserted-by":"crossref","unstructured":"Chang, M.S., Hsieh, S.Y., Chen, G.H.: Dynamic programming on distance-hereditary graphs. In: Proceedings of the International Symposium on Algorithms and Computation, pp. 344\u2013353 (1997)","DOI":"10.1007\/3-540-63890-3_37"},{"key":"1171_CR15","doi-asserted-by":"crossref","unstructured":"Chaudhary, J., Pradhan, D.: Roman $$\\{3\\}$$-domination in graphs: Complexity and algorithms. Discrete Appl. Math. (2022)","DOI":"10.1016\/j.dam.2022.09.017"},{"key":"1171_CR16","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.dam.2015.11.013","volume":"204","author":"M Chellali","year":"2016","unstructured":"Chellali, M., Haynes, T.W., Hedetniemi, S.T., McRae, A.A.: Roman $$\\{2\\}$$-domination. Discrete Appl. Math. 204, 22\u201328 (2016)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.7151\/dmgt.2067","volume":"39","author":"H Chen","year":"2019","unstructured":"Chen, H., Lu, C.: A Note on Roman $$\\{2\\}$$-domination problem in graphs. Discuss. Math. Graph Theory 39, 13\u201321 (2019)","journal-title":"Discuss. Math. Graph Theory"},{"key":"1171_CR18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"1171_CR19","doi-asserted-by":"crossref","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., Jr., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Math. 278, 11\u201322 (2004)","journal-title":"Discrete Math."},{"key":"1171_CR20","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, ACM, New York, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"1171_CR21","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1137\/0217032","volume":"17","author":"A D\u2019Atri","year":"1988","unstructured":"D\u2019Atri, A., Moscarini, M.: Distance-hereditary graphs, steiner trees, and connected domination. SIAM J. Comput. 17, 521\u2013538 (1988)","journal-title":"SIAM J. Comput."},{"key":"1171_CR22","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"1171_CR23","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/net.1","volume":"37","author":"N Falk","year":"2001","unstructured":"Falk, N., Thomas, S.: Homogeneous sets and domination: a linear time algorithm for distance-hereditary graphs. Networks 37, 117\u2013128 (2001)","journal-title":"Networks"},{"key":"1171_CR24","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M Farber","year":"1985","unstructured":"Farber, M., Keil, J.M.: Domination in permutation graphs. J. Algorithms 6, 309\u2013321 (1985)","journal-title":"J. Algorithms"},{"key":"1171_CR25","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"1171_CR26","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"M Haiko","year":"1987","unstructured":"Haiko, M., Brandst\u00e4dt, A.: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theor. Comput. Sci. 53, 257\u2013265 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"1171_CR27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely separable graphs. Discrete Appl. Math. 27, 85\u201399 (1990)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR28","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.dam.2019.01.038","volume":"260","author":"TW Haynes","year":"2019","unstructured":"Haynes, T.W., Henning, M.A.: Perfect Italian domination in trees. Discrete Appl. Math. 260, 164\u2013177 (2019)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR29","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.dam.2016.09.035","volume":"217","author":"MA Henning","year":"2017","unstructured":"Henning, M.A., Klostermeyer, W.F.: Italian domination in trees. Discrete Appl. Math. 217, 557\u2013564 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR30","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.dam.2017.10.027","volume":"236","author":"MA Henning","year":"2018","unstructured":"Henning, M.A., Klostermeyer, W.F., MacGillivray, G.: Perfect Roman domination in trees. Discrete Appl. Math. 236, 235\u2013245 (2018)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR31","first-page":"488","volume":"15","author":"SY Hsieh","year":"2002","unstructured":"Hsieh, S.Y., Ho, C.W., Hsu, T.S., Ko, M.T., Chen, G.H.: Characterization of efficiently parallel solvable problems on distance-hereditary graphs. Discrete Math. 15, 488\u2013518 (2002)","journal-title":"Discrete Math."},{"key":"1171_CR32","unstructured":"Hsu, C.H., Liu, C.S., Peng, S.L.: Roman domination on block graphs. In: Proceedings of the 22nd Workshop on Combinatorial Mathematics and Computation Theory, pp. 188\u2013191 (2005)"},{"key":"1171_CR33","unstructured":"Jamison, R.E., Laskar, R.: Elimination orderings of chordal graphs. In: Proceedings of the Seminar on Combinatorics and Applications, pp. 192\u2013200 (1982)"},{"key":"1171_CR34","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1016\/j.dam.2005.07.011","volume":"154","author":"CM Lee","year":"2006","unstructured":"Lee, C.M., Chang, M.S.: Distance-hereditary graphs are clique-perfect. Discrete Appl. Math. 154, 525\u2013536 (2006)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR35","doi-asserted-by":"crossref","first-page":"3400","DOI":"10.1016\/j.dam.2008.01.011","volume":"156","author":"M Liedloff","year":"2008","unstructured":"Liedloff, M., Kloks, T., Liu, J., Peng, S.L.: Efficient algorithms for Roman domination on some classes of graphs. Discrete Appl. Math. 156, 3400\u20133415 (2008)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR36","doi-asserted-by":"crossref","first-page":"2809","DOI":"10.1007\/s00453-020-00705-7","volume":"82","author":"CC Lin","year":"2020","unstructured":"Lin, C.C., Ku, K.C., Hsu, C.H.: Paired-Domination Problem on Distance-Hereditary Graphs. Algorithmica 82, 2809\u20132840 (2020)","journal-title":"Algorithmica"},{"key":"1171_CR37","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s12190-020-01345-4","volume":"64","author":"C Padamutham","year":"2020","unstructured":"Padamutham, C., Palagiri, V.S.R.: Algorithmic aspects of Roman domination in graphs. J. Appl. Math. Comput. 64, 89\u2013102 (2020)","journal-title":"J. Appl. Math. Comput."},{"key":"1171_CR38","doi-asserted-by":"crossref","first-page":"1081","DOI":"10.1016\/j.akcej.2020.01.005","volume":"17","author":"C Padamutham","year":"2020","unstructured":"Padamutham, C., Palagiri, V.S.R.: Complexity of Roman $$\\{2\\}$$-domination and the double Roman domination in graphs. AKCE Int. J. Graphs Comb. 17, 1081\u20131086 (2020)","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"1171_CR39","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"BS Panda","year":"2003","unstructured":"Panda, B.S., Das, S.K.: A linear time recognition algorithm for proper interval graphs. Inf. Process. Lett. 87, 153\u2013161 (2003)","journal-title":"Inf. Process. Lett."},{"key":"1171_CR40","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.tcs.2022.02.006","volume":"911","author":"A Poureidi","year":"2022","unstructured":"Poureidi, A.: Algorithm and hardness results in double Roman domination of graphs. Theor. Comput. Sci. 911, 70\u201379 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1171_CR41","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/j.dam.2021.08.020","volume":"319","author":"D Pradhan","year":"2022","unstructured":"Pradhan, D., Banerjee, S., Liu, J.B.: Perfect Italian domination in graphs: Complexity and algorithms. Discrete Appl. Math. 319, 271\u2013295 (2022)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR42","first-page":"133","volume":"54","author":"NJ Rad","year":"2012","unstructured":"Rad, N.J., Liu, C.H.: Trees with strong equality between the Roman domination number and the unique response Roman domination number. Australas. J. Comb. 54, 133\u2013140 (2012)","journal-title":"Australas. J. Comb."},{"key":"1171_CR43","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G Ramalingam","year":"1988","unstructured":"Ramalingam, G., Rangan, C.P.: A unified approach to domination problems on interval graphs. Inf. Process. Lett. 27, 271\u2013274 (1988)","journal-title":"Inf. Process. Lett."},{"key":"1171_CR44","doi-asserted-by":"crossref","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. Monthly 107, 585\u2013594 (2000)","journal-title":"Am. Math. Monthly"},{"key":"1171_CR45","unstructured":"Rout, S., Das, G.K.: Roman Domination in Convex Bipartite Graphs. arXiv 2021, arXiv:2111.09040v1"},{"key":"1171_CR46","doi-asserted-by":"crossref","first-page":"3194","DOI":"10.1016\/j.disc.2007.03.020","volume":"307","author":"RR Rubalcaba","year":"2007","unstructured":"Rubalcaba, R.R., Slater, P.J.: Roman dominating influence parameters. Discrete Math. 307, 3194\u20133200 (2007)","journal-title":"Discrete Math."},{"key":"1171_CR47","doi-asserted-by":"crossref","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":"1171_CR48","doi-asserted-by":"crossref","first-page":"1110","DOI":"10.1016\/j.dam.2011.03.013","volume":"159","author":"EE Targhi","year":"2011","unstructured":"Targhi, E.E., Rad, N.J., Volkmann, L.: Unique response Roman domination in graphs. Discrete Appl. Math. 159, 1110\u20131117 (2011)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR49","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0166-218X(98)00060-2","volume":"87","author":"HG Yeh","year":"1998","unstructured":"Yeh, H.G., Chang, G.J.: Weighted connected domination and Steiner trees in distance-hereditary graphs. Discrete Appl. Math. 87, 245\u2013253 (1998)","journal-title":"Discrete Appl. Math."},{"key":"1171_CR50","first-page":"669","volume":"338","author":"J Yue","year":"2018","unstructured":"Yue, J., Wei, M., Li, M., Liu, G.: On the double Roman domination of graphs. Appl. Math. Comput. 338, 669\u2013675 (2018)","journal-title":"Appl. Math. Comput."},{"key":"1171_CR51","doi-asserted-by":"crossref","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.: Double Roman domination in trees. Inf. Process. Lett. 134, 31\u201334 (2018)","journal-title":"Inf. Process. Lett."},{"key":"1171_CR52","first-page":"165","volume":"105","author":"N Zhao","year":"2018","unstructured":"Zhao, N., Li, W., Zhao, T., Zhang, Z.: The unique response Roman domination in trees. J. Combin. Math. Combin. Comput. 105, 165\u2013183 (2018)","journal-title":"J. Combin. Math. Combin. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01171-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01171-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01171-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T13:05:24Z","timestamp":1699621524000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01171-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,4]]},"references-count":52,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1171"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01171-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,4]]},"assertion":[{"value":"9 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2023","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 do not have any financial or non financial interests that are directly or indirectly related to the work submitted for publication.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}