  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 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 it exploits new insight on the combinatorial structure of
Robinsonian matrices. For an $n\times n$ nonnegative matrix with $m$ nonzero
entries, it terminates in $n-1$ SFS sweeps, with overall running time $O(n^2
+nm\log n)$.
