Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition

Monique Laurent, Matteo Seminaroti

We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that…