1
$\begingroup$

Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this purpose? please help.

$\endgroup$
1
$\begingroup$

The binary equivalence relation induces an undirected graph: each item corresponds to a vertex, and draw an edge between each pair of equivalent items. Now compute the connected components of this graph (this can be done in linear time using algorithms based on DFS). Each connected component is a single subset in the partition.

$\endgroup$
  • $\begingroup$ so complexity would be O(|A|)? $\endgroup$ – Shuvra Chakraborty Apr 19 at 14:45
  • $\begingroup$ @ShuvraChakraborty, the running time would be $O(|A| + |R|)$. $\endgroup$ – D.W. Apr 19 at 15:37
  • $\begingroup$ thank you so much. May I get a reference, please? $\endgroup$ – Shuvra Chakraborty Apr 19 at 17:21
  • $\begingroup$ @ShuvraChakraborty, you can use the "cite" button above to reference this post. This is basic undergraduate-level material, so I wouldn't expect there to be a research paper on it, but you might be able to find it in undergraduate algorithms textbooks -- I don't know; that's something you'd have to look for if you care. $\endgroup$ – D.W. Apr 19 at 18:27

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.