Recognition of Robinsonian dissimilarities

DOI10.1007/s003579900015zbMath0905.92036OpenAlexW1994466493MaRDI QIDQ1378872

Bernard Fichet, Victor Chepoi

Publication date: 9 February 1998

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

Full work available at URL: https://doi.org/10.1007/s003579900015

zbMATH Keywords

Robinsonian dissimilaritiesdivide-and-conquer algorithmorder compatible with a dissimilarity

Mathematics Subject Classification ID

Clustering in the social and behavioral sciences (91C20) Applications of graph theory (05C90) Hypergraphs (05C65) Complexity and performance of numerical algorithms (65Y20) Software, source code, etc. for problems pertaining to biology (92-04)

Related Items

An optimal algorithm to recognize Robinsonian dissimilarities ⋮ A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ 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 ⋮ Modules in Robinson Spaces ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ On Robinsonian dissimilarities, the consecutive ones property and latent variable models ⋮ \texttt{PQser:} a Matlab package for spectral seriation ⋮ A structural characterization for certifying Robinsonian matrices ⋮ Combinatorial optimisation and hierarchical classifications ⋮ 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 ⋮ Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Mathematical classification and clustering
• SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item