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

Monique Laurent, Matteo Seminaroti

Research output: Working paperOther research output

43 Downloads (Pure)

Abstract

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).
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages35
Publication statusPublished - Jan 2016

Publication series

NamearXiv
Volume1601.03521

Keywords

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

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.

Cite this