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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ What do you mean "edges being checked"? I don't understand the problem statement. $\endgroup$– quicksortMar 17, 2017 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$– sortegaMar 17, 2017 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$– quicksortMar 17, 2017 at 17:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You are looking for the minimum spanning tree for each connected component.
