An Optimal Algorithm for Strict Circular Seriation

DOI10.1137/21M139356XMaRDI QIDQ5018899zbMATH OpenOpenAlexFDO

Authors Santiago Armstrong, Cristóbal Guzmán, Carlos Sing-Long

Publication date 27 December 2021

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

generative modelcircular-arc hypergraphs\(PQ\)-treescircular embeddings of graphscircular Robinson dissimilaritiescircular Robinsonian matricescircular seriation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic models, generic numerical methods in probability and statistics (65C20) General topics of discrete mathematics in relation to computer science (68R01) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Recommendations

• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Optimal rates of statistical seriation
• Convex relaxations for permutation problems
• An experimental comparison of seriation methods for one-mode two-way data
• The seriation problem in the presence of a double Fiedler value

Cites work

• scientific article; zbMATH DE number 3843553 (Why is no real title available?)
• scientific article; zbMATH DE number 3679885 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• A NEW MEASURE OF RANK CORRELATION
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• An optimal algorithm to recognize Robinsonian dissimilarities
• Circular representation problem on hypergraphs
• Circular-arc hypergraphs: rigidity via connectedness
• Continuation methods for approximate large scale object sequencing
• Cyclically ordered sets
• Graph Laplacian Tomography From Unknown Random Projections
• Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices
• Incidence matrices and interval graphs
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Matrix characterizations of circular-arc graphs
• Optimal Permutation Recovery in Permuted Monotone Matrix Model
• Recognition of Robinsonian dissimilarities
• Seriation and matrix reordering methods: An historical overview
• 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(6)

• Seriation using tree-penalized path length
• A Simple and Optimal Algorithm for Strict Circular Seriation
• Modules in Robinson Spaces
• A generalized insertion algorithm for the seriation problem
• The seriation problem in the presence of a double Fiedler value
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem

This page was built for publication: An Optimal Algorithm for Strict Circular Seriation

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