An optimal algorithm to recognize Robinsonian dissimilarities

DOI10.1007/s00357-014-9150-2zbMath1360.68887OpenAlexW2040277794MaRDI QIDQ269174

Dominique Fortin, Pascal Préa

Publication date: 18 April 2016

Published in: Journal of Classification (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00357-014-9150-2

zbMATH Keywords

seriationclassificationinterval graphsconsecutive one's propertypartition refinementPQ-treesRobinsonian dissimilarities

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Testing a mixture model of single-peaked preferences ⋮ Cut norm discontinuity of triangular truncation of graphons ⋮ Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem ⋮ Robinsonian matrices: recognition challenges ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ The seriation problem in the presence of a double Fiedler value ⋮ Graph sequences sampled from Robinson graphons ⋮ Modules in Robinson Spaces ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ Splitting metrics by \(T_0\)-quasi-metrics ⋮ \texttt{PQser:} a Matlab package for spectral seriation ⋮ Splitting ultra-metrics by \(T_{0}\)-ultra-quasi-metrics ⋮ A structural characterization for certifying Robinsonian matrices ⋮ The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ The weighted sitting closer to friends than enemies problem in the line ⋮ An Optimal Algorithm for Strict Circular Seriation

Uses Software

• PermutMatrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Recognition of Robinsonian dissimilarities
• NP-hard approximation problems in overlapping clustering.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Doubly lexical ordering of dense 0--1 matrices
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Relationship-Based Clustering and Visualization for High-Dimensional Data Mining
• Three Partition Refinement Algorithms
• SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
• A Characterization of Comparability Graphs and of Interval Graphs