# Similarity-first search: A new algorithm with application to Robinsonian matrix recognition

Monique Laurent, Matteo Seminaroti

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

## Abstract

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 the 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)$.

Original language English 1765–1800 SIAM Journal on Discrete Mathematics 31 3 https://doi.org/10.1137/16M1056791 Published - 2017

## Keywords

• Robinson (dis)similarity
• seriation
• similarity search
• Lex-BFS
• LBFS
• partition refinement

## Fingerprint

Dive into the research topics of 'Similarity-first search: A new algorithm with application to Robinsonian matrix recognition'. Together they form a unique fingerprint.
• ### Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition

Laurent, M. & Seminaroti, M., Jan 2016, Ithaca: Cornell University Library, 35 p. (arXiv; vol. 1601.03521).

Research output: Working paperOther research output

File