{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T19:28:44Z","timestamp":1774466924742,"version":"3.50.1"},"reference-count":13,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7223,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1987,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Locating\u2010dominating sets are of interest in safeguard applications of graphical models of facilities. A subset <jats:italic>S<\/jats:italic> of the vertex set <jats:italic>V<\/jats:italic> of a graph <jats:italic>G<\/jats:italic> is a dominating set if each vertex <jats:italic>u \u03f5 V \u2010 S<\/jats:italic> is adjacent to at least one vertex in <jats:italic>S.<\/jats:italic> For each <jats:italic>v<\/jats:italic> in <jats:italic>V \u2010 S<\/jats:italic> let <jats:italic>S(v)<\/jats:italic> denote the set of vertices in <jats:italic>S<\/jats:italic> which are adjacent to <jats:italic>v.<\/jats:italic> A dominating set <jats:italic>S<\/jats:italic> is defined to be \u201clocating\u201d if for any two vertices <jats:italic>v<\/jats:italic> and <jats:italic>w<\/jats:italic> in <jats:italic>V \u2010 S<\/jats:italic> one has <jats:italic>S(v)<\/jats:italic> \u2260 <jats:italic>S(w)<\/jats:italic>. Sharp bounds on the cardinality of locating\u2010dominating sets for arbitrary graphs on <jats:italic>p<\/jats:italic> vertices and for trees on <jats:italic>p<\/jats:italic> vertices are given, and a linear (that is <jats:italic>O(P))<\/jats:italic> algorithm for finding a minimum cardinality locating\u2010dominating set in an acyclic graph is presented.<\/jats:p>","DOI":"10.1002\/net.3230170105","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T21:50:28Z","timestamp":1178920228000},"page":"55-64","source":"Crossref","is-referenced-by-count":143,"title":["Domination and location in acyclic graphs"],"prefix":"10.1002","volume":"17","author":[{"given":"Peter J.","family":"Slater","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90011-3"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070305"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_5_2","first-page":"191","article-title":"The metric basis of a graph","volume":"2","author":"Harary F.","year":"1976","journal-title":"Ars Combinatoria"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.2172\/5313603"},{"key":"e_1_2_1_7_2","volume-title":"Computing Minimum Cost Fire Protection. SAND82\u20130809","author":"Hulme B. L.","year":"1982"},{"key":"e_1_2_1_8_2","article-title":"A Boolean algebraic analysis of fire protection","author":"Hulme B. L.","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_9_2","first-page":"334","volume-title":"Fundamental Algorithms","author":"Knuth D. E.","year":"1968"},{"key":"e_1_2_1_10_2","article-title":"Theory of Graphs","volume":"38","author":"Ore O.","year":"1962","journal-title":"Amer. Math. Soc. Colloq. Publ."},{"key":"e_1_2_1_11_2","unstructured":"P. J.Slater Leaves of tree. Proc. of the Sixth S. E. Conf. on Combinatorics Graph Theory and Computing Utilitas Math. (1975)549\u2013559."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321964"},{"key":"e_1_2_1_13_2","unstructured":"P. J.Slater Dominating and reference sets in a graph. To appear."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T12:23:00Z","timestamp":1697890980000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170105"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170105","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,1]]}}}