Median of 3 Permutations, 3-Cycles and 3-Hitting Set Problem
| Autor: | Sylvie Hamel, Adeline Pierrot, Robin Milosz |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Combinatorics
Set (abstract data type) Permutation Mathematics::Combinatorics 010201 computation theory & mathematics Computer science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology Link (knot theory) 01 natural sciences |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319946665 IWOCA |
| DOI: | 10.1007/978-3-319-94667-2_19 |
| Popis: | The median of permutations problem consists in finding a consensus permutation of a given set of m permutations of size n. This consensus represent the “closest” permutation to the given set under the Kendall-tau distance. Since the complexity of this problem is still unknown for sets of 3 permutations, in the following work, we investigate this specific case and show an interesting link with the 3-Hitting Set problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|