A Lex-BFS-based recognition algorithm for Robinsonian matrices
Presented at the International Conference on Algorithms and Complexity, Paris
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.
|Keywords||Robinson (dis)similarity, unit interval graph, Lex-BFS, seriation, partition refinement, straight enumeration|
|THEME||Life Sciences (theme 5)|
|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)|
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.