Question: How to find Minimum dominating set in a biological network
0
gravatar for Bioinformatist Newbie
4.2 years ago by
Germany
Bioinformatist Newbie240 wrote:

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

 

graph R • 1.3k views
ADD COMMENTlink modified 4.2 years ago by Kamil1.9k • written 4.2 years ago by Bioinformatist Newbie240
1
gravatar for Kamil
4.2 years ago by
Kamil1.9k
Boston
Kamil1.9k wrote:

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 COMMENTlink modified 4.2 years ago • written 4.2 years ago by Kamil1.9k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1526 users visited in the last hour