We present a new ecient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultane- ously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and, for an nn nonnegative matrix with m nonzero entries, it terminates in n &#x100000; 1 SFS sweeps, with overall running time O(n2 + nmlog n).
['Monique Laurent', 'Matteo Seminaroti']
Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition