How to find Minimum dominating set in a biological network
1
0
Entering edit mode
6.2 years ago

How we can find a Minimum Dominating Set (MDS) in a directed network in R ?

 

graph R • 1.7k views
ADD COMMENT
1
Entering edit mode
6.2 years ago
Kamil ★ 2.1k

You might consider describing a specific scientific question. Perhaps searching for a minimum dominating set is one possible approach, but there might be alternative ways to address your question of interest.

 

This package may be interesting: https://cran.r-project.org/web/packages/cccd/

 

This paper might be of interest to you:

http://dx.doi.org/10.1038/srep01736

"Since finding the MDS is NP-hard, we approximate the exact solution by using a sequential greedy algorithm. Starting with an empty set   , at each step the algorithm adds that node to   which yields the largest increase in the number of dominated nodes in the network. When there are multiple candidate nodes yielding the maximal increase in domination, the algorithm chooses one randomly (uniformly among candidates). These steps continue until all nodes are dominated and then the algorithm terminates with   storing the approximated MDS. The greedy algorithm yields a (1 + log N) approximation28 to the size of MDS, and has a time complexity of O(E). See the Supplementary Information for implementation details."

ADD COMMENT

Login before adding your answer.

Traffic: 1486 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6