A Simple and Optimal Algorithm for Strict Circular Seriation

DOI10.1137/22M1495342MaRDI QIDQ5888295zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Guyslain Naves, Pascal Préa

Publication date 24 April 2023

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

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

zbMATH Keywords

hypercyclecircular seriationcircular compatible ordercircular Robinson matrix

Mathematics Subject Classification ID

Computational aspects of data analysis and big data (68T09) Nonnumerical algorithms (68W05) General topics of discrete mathematics in relation to computer science (68R01) Metric embeddings as related to computational problems and algorithms (68R12)

Cites work

• scientific article; zbMATH DE number 3843553 (Why is no real title available?)
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• An Optimal Algorithm for Strict Circular Seriation
• An optimal algorithm to recognize Robinsonian dissimilarities
• Circular representation problem on hypergraphs
• Graph Laplacian Tomography From Unknown Random Projections
• Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices
• Linear and circular unidimensional scaling for symmetric proximity matrices
• NP-hard approximation problems in overlapping clustering.
• PC trees and circular-ones arrangements.
• 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
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The seriation problem in the presence of a double Fiedler value

Cited in

(4)

• Modules in Robinson Spaces
• Extending Robinson spaces: complexity and algorithmic solutions for non-symmetric dissimilarity spaces
• A generalized insertion algorithm for the seriation problem
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem

This page was built for publication: A Simple and 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 Q5888295)