@techreport{8468be57ed46400c9c0e7d316f21f8c8,
title = "Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition",
abstract = "We present a new ecient combinatorial algorithm for recognizing if a givensymmetric 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).",
keywords = "Robinson (dis)similarity, partition refinement, seriation, Lex-BFS, LBFS, Similarity Search",
author = "Monique Laurent and Matteo Seminaroti",
year = "2016",
month = jan,
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",
}