Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?
2
$\begingroup$
$\endgroup$
-
2$\begingroup$ What do you mean "edges being checked"? I don't understand the problem statement. $\endgroup$ – quicksort Mar 17 '17 at 16:46
-
$\begingroup$ By "checking an edge" I mean that there is a cost associated to knowing if the edge between two vertices actually exists. $\endgroup$ – sortega Mar 17 '17 at 17:01
-
1$\begingroup$ Do we know all the costs in advance? Is it like "you can pay $c_{uv}$ to see whether $(u, v) \in E$"? Also, how do you score solutions? What is the "lowest possible cost"? The lowest for which you can exhibit a proof certificate? $\endgroup$ – quicksort Mar 17 '17 at 17:09
2
$\begingroup$
$\endgroup$
You are looking for the minimum spanning tree for each connected component.
