An Optimal Algorithm To Recognize Robinsonian Dissimilarities |
| |
Authors: | Pascal Préa Dominique Fortin |
| |
Institution: | 1. école Centrale Marseille, Marseille, France 3. LIF, Laboratoire d’Informatique Fondamentale de Marseille CNRS UMR 7279, école Centrale Marseille, Technop?le de Chateau-Gombert, 38, rue Joliot Curie, 13451, Marseille Cédex 20, France 2. INRIA, Paris, France
|
| |
Abstract: | A dissimilarity D on a finite set S is said to be Robinsonian if S can be totally ordered in such a way that, for every i < j < k, D (i, j) ≤ D (i, k) and D (j, k) ≤ D (i, k). Intuitively, D is Robinsonian if S can be represented by points on a line. Recognizing Robinsonian dissimilarities has many applications in seriation and classification. In this paper, we present an optimal O (n 2) algorithm to recognize Robinsonian dissimilarities, where n is the cardinal of S. Our result improves the already known algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|