The smallest possible subset of nodes linked to every nodes (a variant of the minimum vertex cover?)

Asked Apr 06 '21 at 14:13

Active Apr 06 '21 at 14:13

Viewed 15 times

I am actually working with non-weighted, undirected graphs. I am looking for algorithms efficient in the research of the smallest possible subset of nodes of the initial graph that "touches" every other nodes (or contains it). In a clique, any node would be the best solution.

In this graph : there would be a multitude of solutions such as [1,4], [4,5], [2,6], etc. It reminds me a lot of the minimum vertex coverage problem but I can't find anything about "node coverage". Has it a specific name ? Is this a common variant of the minimum vertex cover ?

asked Apr 06 '21 at 14:13

Nosk

https://en.wikipedia.org/wiki/Dominating_set – David Eisenstat Apr 06 '21 at 14:15
(use mixed integer programming) – David Eisenstat Apr 06 '21 at 14:16
Thank you I couldn't find the name of my problem. https://stackoverflow.com/questions/40471747/finding-minimum-indepedent-dominating-set-using-a-greedy-algorithm is a more appropriate question. – Nosk Apr 06 '21 at 14:25

The smallest possible subset of nodes linked to every nodes (a variant of the minimum vertex cover?)

0 Answers0