Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition

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 􀀀 1 SFS sweeps, with overall running time O(n2 + nmlog n).