This sounds like Connected Dominating Set.
How to find the minimum number of vertices to join disconnected components of a graph?
-
30-07-2022 - |
Question
Suppose, i have a graph with fixed number of nodes and edges. However, all the nodes doesn't remain active all the time causing the graph disconnected. In this sort of situation, i want to find out the minimal set of vertices, which in case of remaining active, will keep the graph connected all the time.
How can i solve this problem? Can this problem be mapped to any know problem?
Solution
OTHER TIPS
I think that you are looking for the set of articulation points in a graph!
if so, this is an application of Depth-First Search:
http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow