{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T06:55:10Z","timestamp":1758264910380,"version":"3.41.2"},"reference-count":11,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p> Let [Formula: see text] be a graph. A subset [Formula: see text] is a dominating set of [Formula: see text] if for each [Formula: see text] there is a vertex [Formula: see text] adjacent to [Formula: see text]. A dominating set [Formula: see text] of [Formula: see text] is a secure dominating set of [Formula: see text] if for each [Formula: see text] there is a vertex [Formula: see text] adjacent to [Formula: see text] such that [Formula: see text] is also a dominating set of [Formula: see text]. The minimum cardinality of a secure dominating set of [Formula: see text] is called the secure domination number of [Formula: see text]. <\/jats:p><jats:p> Burger et al. [A linear algorithm for secure domination in trees, Discrete Appl. Math.\u00a0171 (2014) 15\u201327] proposed a nontrivial algorithm for computing a minimum secure dominating set of a given tree in linear time and space. In this paper, we give a dynamic programming algorithm to compute the secure domination number of a given tree [Formula: see text] in [Formula: see text] time and space and then using a backtracking search algorithm we can find a minimum secure dominating set of [Formula: see text] in [Formula: see text] time and space that its implementation is much simpler than the implementation of the algorithm proposed by Burger et al. <\/jats:p>","DOI":"10.1142\/s1793830921500555","type":"journal-article","created":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T15:19:25Z","timestamp":1604848765000},"source":"Crossref","is-referenced-by-count":6,"title":["On computing secure domination of trees"],"prefix":"10.1142","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2506-0590","authenticated-orcid":false,"given":"Abolfazl","family":"Poureidi","sequence":"first","affiliation":[{"name":"Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran"}]}],"member":"219","published-online":{"date-parts":[[2020,12,3]]},"reference":[{"doi-asserted-by":"publisher","key":"S1793830921500555BIB001","DOI":"10.1142\/S1793830917500501"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB002","DOI":"10.1016\/j.dam.2016.03.017"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB003","DOI":"10.11650\/twjm\/1500602498"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB004","DOI":"10.1016\/j.dam.2014.02.001"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB005","DOI":"10.1016\/j.dam.2015.11.013"},{"key":"S1793830921500555BIB006","first-page":"19","volume":"67","author":"Cockayne E. J.","year":"2005","journal-title":"Util. Math."},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB007","DOI":"10.1142\/S1793830919500551"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB008","DOI":"10.1142\/S1793830916500671"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB009","DOI":"10.1080\/00029890.2000.12005243"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB010","DOI":"10.1038\/scientificamerican1299-136"},{"doi-asserted-by":"publisher","key":"S1793830921500555BIB011","DOI":"10.1016\/j.ins.2010.07.001"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500555","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,14]],"date-time":"2021-10-14T03:59:10Z","timestamp":1634183950000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500555"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,3]]},"references-count":11,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.1142\/S1793830921500555"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500555","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2020,12,3]]},"article-number":"2150055"}}