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...

Fuld beskrivelse

Enregistré dans:
Bibliografiske detaljer
Udgivet i:URI:https://journals.openedition.org/msh,
Hovedforfatter: Hudry, Olivier
Format: Article ou chapitre numérique
Sprog:Français
Udgivet: Mathématiques et sciences humaines 2012
Fag:
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 adgang: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

Lignende værker