2
$\begingroup$

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?

|cite|improve this question
$\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$

You are looking for the minimum spanning tree for each connected component.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.