NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)

NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)

Étant donnée une collection de relations d’équivalence (ou partitions), le problème de Régnier consiste à déterminer une relation d’équivalence qui minimise l’éloignement par rapport à . L’éloignement est fondé sur la distance de la différence symétrique et mesure le nombre de désaccords entre  et...

Ful tanımlama

Kaydedildi:
Detaylı Bibliyografya
Yayımlandı:URI:https://journals.openedition.org/msh,
Yazar: Hudry, Olivier
Materyal Türü: Article ou chapitre numérique
Dil:Français
Baskı/Yayın Bilgisi: Mathématiques et sciences humaines 2012
Konular:
classification
relation
partition
complexity
median
symmetric difference distance
aggregation of relations
equivalence relation
NP-completeness
Régnier’s problem
Zahn’s problem
complexité
aggregation de relations
distance de la difference symétrique
NP-complétude
problem de Régnier
problem de Zahn
relation d’équivalence
relation médiane
Online Erişim:Accès Université d'Orléans et IFPM
Accès Université d'Orléans et IFPM

Internet

https://ezproxy.univ-orleans.fr/login?url=https://doi.org/10.4000/msh.12209
https://ezproxy.univ-orleans.fr/login?url=https://journals.openedition.org/msh/12209

Benzer Materyaller