{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T17:44:11Z","timestamp":1720201451814},"reference-count":42,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1016\/j.tcs.2022.07.020","type":"journal-article","created":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T17:00:43Z","timestamp":1658854843000},"page":"142-156","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":1,"special_numbering":"C","title":["A polynomial-time approximation to a minimum dominating set in a graph"],"prefix":"10.1016","volume":"930","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5480-8257","authenticated-orcid":false,"given":"Frank \u00c1ngel","family":"Hern\u00e1ndez Mira","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-7901-4936","authenticated-orcid":false,"given":"Ernesto","family":"Parra Inza","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 Mar\u00eda","family":"Sigarreta Almira","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9013-9334","authenticated-orcid":false,"given":"Nodari","family":"Vakhania","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/j.tcs.2022.07.020_br0010","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","article-title":"Linear time algorithms for finding a dominating set of fixed size in degenerated graphs","volume":"54","author":"Alon","year":"2009","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2022.07.020_br0020","series-title":"The Theory of Graphs and Its Applications","author":"Berge","year":"1962"},{"key":"10.1016\/j.tcs.2022.07.020_br0030","series-title":"MAICS","first-page":"55","article-title":"Fast Dominating set algorithms for social networks","author":"Campan","year":"2015"},{"issue":"1","key":"10.1016\/j.tcs.2022.07.020_br0040","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1155\/S016117129000031X","article-title":"A note on the k-domination number of a graph","volume":"13","author":"Caro","year":"1990","journal-title":"Int. J. Math. Math. Sci."},{"key":"10.1016\/j.tcs.2022.07.020_br0050","series-title":"European Symposium on Algorithm","first-page":"192","article-title":"Approximation hardness of dominating set problems","author":"Chleb\u00edk","year":"2004"},{"key":"10.1016\/j.tcs.2022.07.020_br0060","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set covering problem","volume":"4","author":"Chv\u00e1tal","year":"1979","journal-title":"Math. Oper. Res."},{"issue":"2","key":"10.1016\/j.tcs.2022.07.020_br0070","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","article-title":"A linear algorithm for the domination number of a tree","volume":"4","author":"Cockayne","year":"1975","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.tcs.2022.07.020_br0080","series-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms","isbn-type":"print","first-page":"718","article-title":"Structural and algorithmic aspects of massive social networks","author":"Eubank","year":"2004","ISBN":"http:\/\/id.crossref.org\/isbn\/089871558X"},{"key":"10.1016\/j.tcs.2022.07.020_br0090","series-title":"Latin American Symposium on Theoretical Informatics","first-page":"747","article-title":"Domination in geometric intersection graphs","author":"Erlebach","year":"2008"},{"key":"10.1016\/j.tcs.2022.07.020_br0100","series-title":"Proceedings of the Meeting on Analytic Algorithmics and Combinatorics","first-page":"25","article-title":"Approximating fault-tolerant domination in general graphs","author":"Foerster","year":"2013"},{"key":"10.1016\/j.tcs.2022.07.020_br0110","series-title":"Conference on Knowledge Discovery and Data Mining","first-page":"150","article-title":"Efficient identification of web communities","author":"Flake","year":"2000"},{"issue":"5","key":"10.1016\/j.tcs.2022.07.020_br0120","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1552285.1552286","article-title":"A measure and conquer approach for the analysis of exact algorithms","volume":"56","author":"Fomin","year":"2009","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2022.07.020_br0130","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"1","key":"10.1016\/j.tcs.2022.07.020_br0140","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/1644015.1644024","article-title":"Exponential time algorithms for the minimum dominating set problem on some graph classes","volume":"6","author":"Gaspers","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"10.1016\/j.tcs.2022.07.020_br0150","author":"Gibson"},{"issue":"03","key":"10.1016\/j.tcs.2022.07.020_br0160","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1142\/S0129054100000260","article-title":"On the clique-width of some perfect graph classes","volume":"11","author":"Golumbic","year":"2000","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"10.1016\/j.tcs.2022.07.020_br0170","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","article-title":"Approximation algorithms for connected dominating sets","volume":"20","author":"Guha","year":"1998","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2022.07.020_br0180","series-title":"Domination in Graphs (Advanced Topics)","isbn-type":"print","author":"Haynes","year":"1998","ISBN":"http:\/\/id.crossref.org\/isbn\/9780824700348"},{"key":"10.1016\/j.tcs.2022.07.020_br0190","isbn-type":"print","article-title":"Fundamentals of Domination in Graphs","volume":"vol. 208","author":"Haynes","year":"1998","ISBN":"http:\/\/id.crossref.org\/isbn\/9780824700331"},{"issue":"1","key":"10.1016\/j.tcs.2022.07.020_br0200","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1186\/1471-2105-7-108","article-title":"A quantitative analysis of secondary RNA structure using domination based parameters on trees","volume":"7","author":"Haynes","year":"2006","journal-title":"BMC Bioinform."},{"issue":"2","key":"10.1016\/j.tcs.2022.07.020_br0210","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","article-title":"NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs","volume":"26","author":"Hunt","year":"1998","journal-title":"J. Algorithms"},{"issue":"3","key":"10.1016\/j.tcs.2022.07.020_br0220","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0165-4896(88)90041-8","article-title":"Dominating sets in social network graphs","volume":"16","author":"Kelleher","year":"1988","journal-title":"Math. Soc. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2022.07.020_br0230","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0166-218X(83)90003-3","article-title":"A linear algorithm for the domination number of a series-parallel graph","volume":"5","author":"Kikuno","year":"1983","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"10.1016\/j.tcs.2022.07.020_br0240","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.72.041906","article-title":"Instability of defensive alliances in the predator-prey model on complex networks","volume":"72","author":"Kim","year":"2005","journal-title":"Phys. Rev. E"},{"key":"10.1016\/j.tcs.2022.07.020_br0250","series-title":"Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing","first-page":"300","article-title":"What cannot be computed locally!","author":"Kuhn","year":"2004"},{"issue":"4","key":"10.1016\/j.tcs.2022.07.020_br0260","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","article-title":"Constant-time distributed dominating set approximation","volume":"17","author":"Kuhn","year":"2005","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2022.07.020_br0270","series-title":"On Cliques and Kernels","author":"Lerchs","year":"1971"},{"issue":"5","key":"10.1016\/j.tcs.2022.07.020_br0280","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","article-title":"k-Degenerate graphs","volume":"22","author":"Lick","year":"1970","journal-title":"Can. J. Math."},{"issue":"4","key":"10.1016\/j.tcs.2022.07.020_br0290","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/1383369.1383380","article-title":"Approximation schemes for wireless networks","volume":"4","author":"Nieberg","year":"2008","journal-title":"ACM Trans. Algorithms"},{"key":"10.1016\/j.tcs.2022.07.020_br0300","article-title":"Theory of graphs","volume":"38","author":"Ore","year":"1962","journal-title":"Colloq. Publ. \u2013 Am. Math. Soc."},{"issue":"5","key":"10.1016\/j.tcs.2022.07.020_br0310","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(91)90021-9","article-title":"Analysis of a greedy heuristic for finding small dominating sets in graphs","volume":"39","author":"Parekh","year":"1991","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.tcs.2022.07.020_br0320","series-title":"Proc. on 255th of the USA Military Academy","first-page":"1350","article-title":"Alliance in graph","author":"Powel","year":"2004"},{"key":"10.1016\/j.tcs.2022.07.020_br0330","article-title":"The secure domination problem in cographs","author":"Pradhan","year":"2019","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.tcs.2022.07.020_br0340","series-title":"STOC, vol. 97","first-page":"475","article-title":"A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP","author":"Raz","year":"1997"},{"key":"10.1016\/j.tcs.2022.07.020_br0350","series-title":"Centrum voor Wiskunde en Informatica","article-title":"A new algorithm for the recognition of series parallel graphs","author":"Schoenmakers","year":"1995"},{"key":"10.1016\/j.tcs.2022.07.020_br0360","doi-asserted-by":"crossref","DOI":"10.1016\/j.ipl.2019.01.006","article-title":"Greedy domination on biclique-free graphs","author":"Siebertz","year":"2019","journal-title":"Inf. Process. Lett."},{"issue":"17","key":"10.1016\/j.tcs.2022.07.020_br0370","doi-asserted-by":"crossref","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","article-title":"Exact algorithms for dominating set","volume":"159","author":"Van Rooij","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2022.07.020_br0380","series-title":"Approximation Algorithms","author":"Vazirani","year":"2001"},{"key":"10.1016\/j.tcs.2022.07.020_br0390","series-title":"IJCAI","first-page":"1514","article-title":"A fast local search algorithm for minimum weight dominating set problem on massive graphs","author":"Wang","year":"2018"},{"key":"10.1016\/j.tcs.2022.07.020_br0400","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1613\/jair.5205","article-title":"Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function","volume":"58","author":"Wang","year":"2017","journal-title":"J. Artif. Intell. Res."},{"key":"10.1016\/j.tcs.2022.07.020_br0410","series-title":"IJCAI","first-page":"1514","article-title":"A fast local search algorithm for minimum weight dominating set problem on massive graphs","author":"Wang","year":"2018"},{"key":"10.1016\/j.tcs.2022.07.020_br0420","author":"Parra Inza"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439752200442X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439752200442X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T01:20:28Z","timestamp":1712712028000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439752200442X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":42,"alternative-id":["S030439752200442X"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2022.07.020","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2022,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A polynomial-time approximation to a minimum dominating set in a graph","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2022.07.020","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2022 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}