Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Majority graphs of profiles of equivalence relations and complexity of Régnier’s problem

Olivier Hudry 1, 2 
Abstract : A classic problem arising in classication consists in summarizing a collection C, called a profile, of p equivalence relations defined on a finite set X by an equivalence relation E* at minimum remoteness from C. The remoteness is based on the symmetric dierence distance and measures the total number of disagreements between E* and C, and then E* is called a median equivalence relation of C. It is usual to summarize C by its majority graph. We study the converse issue. We give a sufficient condition for a graph to be the majority graph of a profile of equivalence relations. We then deduce from this that the computation of E* is NP-hard when p is large enough.
Complete list of metadata

https://hal.telecom-paris.fr/hal-02286316
Contributor : TelecomParis HAL Connect in order to contact the contributor
Submitted on : Friday, September 13, 2019 - 3:36:18 PM
Last modification on : Monday, January 24, 2022 - 8:26:29 AM

Identifiers

  • HAL Id : hal-02286316, version 1

Citation

Olivier Hudry. Majority graphs of profiles of equivalence relations and complexity of Régnier’s problem. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), May 2012, Munich, Germany. pp.147-150. ⟨hal-02286316⟩

Share

Metrics

Record views

41