Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be re- ordered. 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 non- negative 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.
Additional Metadata
Keywords Robinson (dis)similarity, unit interval graph, Lex-BFS, seriation, partition refinement, straight enumeration
THEME Life Sciences (theme 5)
Publisher Springer
Editor V. Paschos , P. Widmayer
Project Mixed-Integer Nonlinear Optimization
Conference International Conference on Algorithms and Complexity
Note Published paper: DOI: 10.1007/978-3-319-18173-8_24
Grant This work was funded by the European Commission 7th Framework Programme; grant id h2020/764759 - Mixed-Integer Non-Linear Optimisation Applications (MINOA)
Citation
Laurent, M, & Seminaroti, M. (2015). A Lex-BFS-based recognition algorithm for Robinsonian matrices. In V Paschos & P Widmayer (Eds.), Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings (pp. 325–338). Springer.