Calculation of the Connected Dominating Set Considering Vertex Importance Metrics
Open Access
Abstract
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).Keywords
This publication has 22 references indexed in Scilit:
- Structure and dynamics of molecular networks: A novel paradigm of drug discoveryPharmacology & Therapeutics, 2013
- Identification of influential spreaders in complex networksNature Physics, 2010
- A Power Aware Minimum Connected Dominating Set for Wireless Sensor NetworksJournal of Networks, 2009
- Graph theoretical analysis of complex networks in the brainNonlinear Biomedical Physics, 2007
- Distributed algorithms for connected domination in wireless networksJournal of Parallel and Distributed Computing, 2007
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs2006
- Distributed heuristics for connected dominating sets in wireless ad hoc networksJournal of Communications and Networks, 2002
- Exploring complex networksNature, 2001
- Approximation Algorithms for Connected Dominating SetsAlgorithmica, 1998
- Unit disk graphsDiscrete Mathematics, 1990