### Abstract

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

Original language | English |
---|---|

Place of Publication | Ithaca |

Publisher | Cornell University Library |

Number of pages | 35 |

Publication status | Published - Jan 2016 |

### Publication series

Name | arXiv |
---|---|

Volume | 1601.03521 |

### Keywords

- Robinson (dis)similarity
- partition refinement
- seriation
- Lex-BFS
- LBFS
- Similarity Search

### Cite this

*Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition*. (arXiv; Vol. 1601.03521). Ithaca: Cornell University Library.

}

**Similarity-First Search : A New Algorithm With Application to Robinsonian Matrix Recognition.** / Laurent, Monique; Seminaroti, Matteo.

Research output: Working paper › Other research output

TY - UNPB

T1 - Similarity-First Search

T2 - A New Algorithm With Application to Robinsonian Matrix Recognition

AU - Laurent, Monique

AU - Seminaroti, Matteo

PY - 2016/1

Y1 - 2016/1

N2 - 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).

AB - 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).

KW - Robinson (dis)similarity

KW - partition refinement

KW - seriation

KW - Lex-BFS

KW - LBFS

KW - Similarity Search

M3 - Working paper

T3 - arXiv

BT - Similarity-First Search

PB - Cornell University Library

CY - Ithaca

ER -