### Abstract

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

Original language | English |
---|---|

Pages (from-to) | 151-165 |

Journal | Discrete Applied Mathematics |

Volume | 222 |

DOIs | |

Publication status | Published - May 2017 |

### Keywords

- Robinson (dis)similarity
- Unit interval graph
- Lex-BFS
- Seriation
- Partition refinement
- Straight enumeration

## Fingerprint Dive into the research topics of 'A Lex-BFS-based recognition algorithm for Robinsonian matrices'. Together they form a unique fingerprint.

## Cite this

Laurent, M., & Seminaroti, M. (2017). A Lex-BFS-based recognition algorithm for Robinsonian matrices.

*Discrete Applied Mathematics*,*222*, 151-165. https://doi.org/10.1016/j.dam.2017.01.027