Efficient algorithms for clone items detection.
Raoul Medina, Caroline Noyer, Olivier Raynaud · 2005
Abstract. This paper presents efficient algorithms for clone items detection in a binary relation. Best implementation of these algorithms has O(|J|.||M||) time complexity, with J corresponding to the set of items of the relation and ||M| | corresponding to the size of the relation. This result improves the previous algorithm given in [3] which is O(|J | 2.||M||). Clone items have been introduced by Medina and Nourine to explain why, sometimes, the number of rules of a minimum cover of a relation is exponential with the number of items of the relation. 1