Modules in Robinson Spaces

DOI10.1137/22M1494348MaRDI QIDQ6187080zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Guyslain Naves, Pascal Préa

Publication date 10 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.12386

zbMATH Keywords

seriationclassificationdivide-and-conquerRobinson dissimilaritymmodule

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Nonnumerical algorithms (68W05) General topics of discrete mathematics in relation to computer science (68R01) Total orders (06A05)

Abstract: A Robinson space is a dissimilarity space $(X,d)$ (i.e., a set $X$ of size $n$ and a dissimilarity $d$ on $X$) for which there exists a total order $<$ on $X$ such that $x<y<z$ implies that $d(x,z)gemaxd(x,y),d(y,z)$. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of $(X,d)$ (generalizing the notion of a module in graph theory) is a subset $M$ of $X$ which is not distinguishable from the outside of $M$, i.e., the distance from any point of $XsetminusM$ to all points of $M$ is the same. If $p$ is any point of $X$, then $p$ and the maximal by inclusion mmodules of $(X,d)$ not containing $p$ define a partition of $X$, called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal $O(n^2)$ time.

Recommendations

• An optimal algorithm to recognize Robinsonian dissimilarities
• Recognition of Robinsonian dissimilarities
• Robinsonian matrices: recognition challenges

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 3843553 (Why is no real title available?)
• scientific article; zbMATH DE number 4213811 (Why is no real title available?)
• scientific article; zbMATH DE number 3724452 (Why is no real title available?)
• scientific article; zbMATH DE number 802809 (Why is no real title available?)
• A Simple and Optimal Algorithm for Strict Circular Seriation
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
• A structural characterization for certifying Robinsonian matrices
• A survey of the algorithmic aspects of modular decomposition
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• An Optimal Algorithm for Strict Circular Seriation
• An optimal algorithm to recognize Robinsonian dissimilarities
• An optimization parameter for seriation of noisy data
• Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices
• Localization in 1D non-parametric latent space models from pairwise affinities
• NP-hard approximation problems in overlapping clustering.
• Partitive hypergraphs
• Purely Functional Data Structures
• Recognition of Robinsonian dissimilarities
• SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• Spectral ranking using seriation
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Structural Representation of Proximity Matrices with MATLAB
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families

This page was built for publication: Modules in Robinson Spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187080)