An Optimal Algorithm for Strict Circular Seriation
DOI10.1137/21M139356XOpenAlexW3212459243MaRDI QIDQ5018899
Cristóbal Guzmán, Santiago Armstrong, 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
generative modelcircular-arc hypergraphs\(PQ\)-treescircular embeddings of graphscircular Robinson dissimilaritiescircular Robinsonian matricescircular seriation
General topics of discrete mathematics in relation to computer science (68R01) Probabilistic models, generic numerical methods in probability and statistics (65C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
- An optimal algorithm to recognize Robinsonian dissimilarities
- Circular-arc hypergraphs: rigidity via connectedness
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Continuation methods for approximate large scale object sequencing
- Circular representation problem on hypergraphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Recognition of Robinsonian dissimilarities
- Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices
- Incidence matrices and interval graphs
- Matrix characterizations of circular-arc graphs
- Cyclically ordered sets
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Seriation and matrix reordering methods: An historical overview
- Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
- Graph Laplacian Tomography From Unknown Random Projections
- A NEW MEASURE OF RANK CORRELATION
- Optimal Permutation Recovery in Permuted Monotone Matrix Model
This page was built for publication: An Optimal Algorithm for Strict Circular Seriation