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

Monique Laurent, Matteo Seminaroti

Research output: Working paperOther research output

18 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

Cite this

Laurent, M., & Seminaroti, M. (2016). Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition. (arXiv; Vol. 1601.03521). Ithaca: Cornell University Library.
Laurent, Monique ; Seminaroti, Matteo. / Similarity-First Search : A New Algorithm With Application to Robinsonian Matrix Recognition. Ithaca : Cornell University Library, 2016. (arXiv).
@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 = "1",
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",

}

Laurent, M & Seminaroti, M 2016 'Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition' arXiv, vol. 1601.03521, Cornell University Library, Ithaca.

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

Ithaca : Cornell University Library, 2016. (arXiv; Vol. 1601.03521).

Research output: Working paperOther 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 -

Laurent M, Seminaroti M. Similarity-First Search: A New Algorithm With Application to Robinsonian Matrix Recognition. Ithaca: Cornell University Library. 2016 Jan. (arXiv).