2015/04/24 by Monique Laurent, Laurent, Monique, Matteo Seminaroti +1
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1504.06586
openalex publication_date 2015/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm is simple and is based essentially on lexicographic breadth-first search (Lex-BFS), using a divide-and-conquer strategy. When applied to a nonnegative symmetric n× n matrix with~m nonzero entries and given as a weighted adjacency list, it runs in O(d(n+m)) time, where d is the depth of the recursion tree, which is at most the number of distinct nonzero entries of A.