{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T07:40:02Z","timestamp":1738654802579,"version":"3.35.0"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p> Let [Formula: see text] be graph. For any function [Formula: see text], let [Formula: see text], [Formula: see text]. The function [Formula: see text] is called an outer-independent double Roman dominating function (OIDRDF) if the following conditions are satisfied. <\/jats:p><jats:p> <jats:sup>(i)<\/jats:sup> If [Formula: see text], then [Formula: see text] or [Formula: see text] <jats:sup>(ii)<\/jats:sup> If [Formula: see text], then [Formula: see text] <jats:sup>(iii)<\/jats:sup> [Formula: see text] is independent. <\/jats:p><jats:p> The outer-independent double Roman domination number of [Formula: see text] is defined by [Formula: see text] is an OIDRDF OF [Formula: see text]. We prove that the decision problem MOIDRDP, corresponding to [Formula: see text] is NP-complete for split graphs. We also show that it is linear time solvable for connected threshold graphs and bounded treewidth graphs. Finally, we show that the MOIDRDP and domination are not equivalent in computational complexity aspects. <\/jats:p>","DOI":"10.1142\/s0129054124500059","type":"journal-article","created":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T14:30:23Z","timestamp":1711636223000},"page":"25-34","source":"Crossref","is-referenced-by-count":0,"title":["Algorithmic Aspects of Outer-Independent Double Roman Domination in Graphs"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9667-4015","authenticated-orcid":false,"given":"Amit","family":"Sharma","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology Warangal, Warangal 506 004, Telangana, India"}]},{"given":"P. Venkata Subba","family":"Reddy","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology Warangal, Warangal 506 004, Telangana, India"}]},{"given":"S.","family":"Arumugam","sequence":"additional","affiliation":[{"name":"Director, n-CARDMATH, Kalasalingam Academy of Research and Education, Anand Nagar, Krishnankoil, Tamilnadu, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6936-2358","authenticated-orcid":false,"given":"Jakkepalli Pavan","family":"Kumar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology Tiruchirappalli, Tiruchirappalli 620 015, Tamilnadu, India"}]}],"member":"219","published-online":{"date-parts":[[2024,3,28]]},"reference":[{"key":"S0129054124500059BIB001","first-page":"2250004","volume":"14","author":"Amit S.","year":"2022","journal-title":"Disc. Math. Algo. and Appl"},{"key":"S0129054124500059BIB002","first-page":"126662","volume":"414","author":"Ahangar H. A.","year":"2022","journal-title":"Appl. Math. Comput."},{"key":"S0129054124500059BIB003","first-page":"124617","volume":"364","author":"Ahangar H. A.","year":"2020","journal-title":"Appl. Math. Comput."},{"key":"S0129054124500059BIB004","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.2108"},{"key":"S0129054124500059BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"S0129054124500059BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"S0129054124500059BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.043"},{"volume-title":"Domination in Graphs: Advanced Topics","year":"1997","author":"Haynes T. W.","key":"S0129054124500059BIB008"},{"key":"S0129054124500059BIB009","doi-asserted-by":"publisher","DOI":"10.1201\/9781482246582"},{"key":"S0129054124500059BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00811-7"},{"key":"S0129054124500059BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.09.019"},{"volume-title":"Computers and Interactability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Johnson D. S.","key":"S0129054124500059BIB012"},{"key":"S0129054124500059BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-017-0112-6"},{"issue":"1","key":"S0129054124500059BIB014","volume":"41","author":"Pavan Kumar J.","year":"2021","journal-title":"J. Comb. Optim."},{"key":"S0129054124500059BIB015","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.2260"},{"issue":"3","key":"S0129054124500059BIB016","first-page":"153","volume":"28","author":"Pavan Kumar J.","year":"2020","journal-title":"Analele Stiint. Ale Univ. Ovidius Constanta Ser. Mat."},{"volume-title":"Introduction to Graph Theory","year":"2001","author":"West D. B.","key":"S0129054124500059BIB017"},{"volume-title":"Threshold Graphs and Related Topics","year":"1995","author":"Mahadev N.","key":"S0129054124500059BIB018"},{"key":"S0129054124500059BIB019","first-page":"167","volume":"19","author":"Rad N. J.","year":"2019","journal-title":"An. Stiint. Univ. Ovidius Constanta Ser. Mat."},{"key":"S0129054124500059BIB020","volume-title":"Introduction to Algorithms","volume":"6","author":"Leiserson C. E.","year":"2001"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054124500059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T07:19:05Z","timestamp":1738653545000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054124500059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,28]]},"references-count":20,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.1142\/S0129054124500059"],"URL":"https:\/\/doi.org\/10.1142\/s0129054124500059","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2024,3,28]]}}}