**230**wrote:

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

**1.9k**• written 3.7 years ago by Bioinformatist Newbie •

**230**

Question: How to find Minimum dominating set in a biological network

0

Bioinformatist Newbie • **230** wrote:

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

ADD COMMENT
• link
•
modified 3.7 years ago
by
Kamil • **1.9k**
•
written
3.7 years ago by
Bioinformatist Newbie • **230**

1

Kamil • **1.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."

Please log in to add an answer.

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

Powered by Biostar
version 2.3.0

Traffic: 689 users visited in the last hour