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

How to find Minimum dominating set in a biological network

0

Entering edit mode

6.2 years ago

Bioinformatist Newbie
▴
250

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

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."

Similar Posts

Loading Similar Posts

Traffic: 1486 users visited in the last hour

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