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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ so complexity would be O(|A|)? $\endgroup$ Commented Apr 19, 2019 at 14:45
-
$\begingroup$ @ShuvraChakraborty, the running time would be $O(|A| + |R|)$. $\endgroup$– D.W. ♦Commented Apr 19, 2019 at 15:37
-
$\begingroup$ thank you so much. May I get a reference, please? $\endgroup$ Commented Apr 19, 2019 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. ♦Commented Apr 19, 2019 at 18:27