Un algorithme efficace pour reconnaitre les dissimilarités dont tous les chemins de tous les arbres de longueur minimale sont Robinsoniens

International audience ; Étant donné une dissimilarité d sur un ensemble X, un arbre T = (X, E) est compatible avec (X, d) si pour tous x, z ∈ X et tout y sur le chemin entre x et z, d(x, z) ≥ max{d(x, y), d(y, z)}. Si T est compatible avec (X, d), alors T est un arbre de longueur minimale (ALM) de (X, d). Étant donné (X, d) avec |X| = n, nous présentons dans cet article un algorithme en O(n 2 ) pour vérifier si un ALM donné T est compatible (avec (X, d)) et un algorithme en O(n 3 ) qui détermine si tous les ALM de (X, d) sont compatibles. Ceci répond (approximativement) à une question de Brucker (2013).