{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:55:23Z","timestamp":1774418123717,"version":"3.50.1"},"reference-count":22,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,1,28]],"date-time":"2018-01-28T00:00:00Z","timestamp":1517097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The computation of a set constituted by few vertices to define a virtual backbone supporting information interchange is a problem that arises in many areas when analysing networks of different natures, like wireless, brain, or social networks. Recent papers propose obtaining such a set of vertices by computing the connected dominating set (CDS) of a graph. In recent works, the CDS has been obtained by considering that all vertices exhibit similar characteristics. However, that assumption is not valid for complex networks in which their vertices can play different roles. Therefore, we propose finding the CDS by taking into account several metrics which measure the importance of each network vertex e.g., error probability, entropy, or entropy variation (EV).<\/jats:p>","DOI":"10.3390\/e20020087","type":"journal-article","created":{"date-parts":[[2018,1,29]],"date-time":"2018-01-29T07:46:20Z","timestamp":1517211980000},"page":"87","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Calculation of the Connected Dominating Set Considering Vertex Importance Metrics"],"prefix":"10.3390","volume":"20","author":[{"given":"Francisco","family":"Vazquez-Araujo","sequence":"first","affiliation":[{"name":"Department of Computer Engineering, Universidade da Coru\u00f1a, Campus de Elvi\u00f1a, 15071 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7362-6854","authenticated-orcid":false,"given":"Adriana","family":"Dapena","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Universidade da Coru\u00f1a, Campus de Elvi\u00f1a, 15071 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mar\u00eda","family":"Souto-Salorio","sequence":"additional","affiliation":[{"name":"Department of Computation, Universidade da Coru\u00f1a, Campus de Elvi\u00f1a, 15071 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0521-3465","authenticated-orcid":false,"given":"Paula","family":"Castro","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Universidade da Coru\u00f1a, Campus de Elvi\u00f1a, 15071 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,1,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Stam, J.S., and Reijneveld, J. (2007). Graph theoretical analysis of complex networks in the brain. Nonlinear Biomed. Phys., 1.","DOI":"10.1186\/1753-4631-1-3"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1038\/35065725","article-title":"Exploring complex networks","volume":"410","author":"Strogatz","year":"2001","journal-title":"Nature"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1038\/nphys1746","article-title":"Identification of influential spreaders in complex networks","volume":"6","author":"Kitsak","year":"2010","journal-title":"Nat. Phys."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Richardson, M., and Domingos, P. (2002, January 23\u201326). Mining knowledge-sharing sites for viral marketing. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201902), New York, NY, USA.","DOI":"10.1145\/775056.775057"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.pharmthera.2013.01.016","article-title":"Structure and dynamics of molecular networks: A novel paradigm of drug discovery","volume":"138","author":"Csermely","year":"2013","journal-title":"Pharmacol. Ther."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/JCN.2002.6596929","article-title":"Distributed heuristics for connected dominating set in wireless ad hoc networks","volume":"4","author":"Alzoubi","year":"2002","journal-title":"IEEE J. Commun. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Butenko, S., Cheng, S., Du, D., and Pardolos, P.M. (2003). On the construction of virtual backbone for ad hoc wireless network. Cooperative Control: Models, Applications and Algorithms, Springer.","DOI":"10.1007\/978-1-4757-3758-5_3"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","article-title":"Unit disk graphs","volume":"86","author":"Clark","year":"1990","journal-title":"Discrete Math."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Du, D.-Z., and Wan, P.-J. (2013). Connected dominating set: theory and applications, Springer Optimization and its Applications.","DOI":"10.1007\/978-1-4614-5242-3"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","article-title":"Approximation algorithms for connected dominating set","volume":"20","author":"Guha","year":"1998","journal-title":"Algorithmica"},{"key":"ref_11","first-page":"511","article-title":"A Power aware minimum connected dominating set for wireless sensor networks","volume":"4","author":"Rai","year":"2009","journal-title":"J. Netw."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1016\/j.jpdc.2007.04.003","article-title":"Distributed algorithms for connected domination in wireless networks","volume":"67","author":"Gandhi","year":"2007","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/11830924_3","article-title":"Constant-factor approximation for minimum-weight (connect) dominating sets in unit disk graphs","volume":"4110","author":"Erlebach","year":"2006","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s10878-008-9146-0","article-title":"A better constant-factor approximation for weighted dominating set in unit disk graph","volume":"18","author":"Huang","year":"2008","journal-title":"J. Comb. Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1109\/TNET.2016.2607723","article-title":"Approximation algorithm for minimum weight (k,m)-CDS problem in unit disk graph","volume":"25","author":"Shi","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02477860","article-title":"Life, information theory, and topology","volume":"17","author":"Rashevsky","year":"1955","journal-title":"Bull. Math. Biophys."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02476948","article-title":"Entropy and the complexity of graphs: I. An index of the relative complexity of a graph","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"559","DOI":"10.3390\/e14030559","article-title":"Entropy and complexity of graphs revisited","volume":"14","author":"Mowshowitz","year":"2012","journal-title":"Entropy"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kajdanowicz, T., and MMorz, M. (2016). Using graph and vertex entropy to compare empirical graphs with theoretical graph models. Entropy, 18.","DOI":"10.3390\/e18090320"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ai, X. (2017). Node importance ranking of complex networks with entropy variation. Entropy, 19.","DOI":"10.3390\/e19070303"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A Mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2019small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/2\/87\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:52:51Z","timestamp":1760194371000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/2\/87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,28]]},"references-count":22,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,2]]}},"alternative-id":["e20020087"],"URL":"https:\/\/doi.org\/10.3390\/e20020087","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,28]]}}}