A Lex-BFS-based recognition algorithm for Robinsonian matrices

Monique Laurent, M. Seminaroti

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

Abstract

Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm is simple and is based essentially on lexicographic breadth-first search (Lex-BFS), using a divide-and-conquer strategy. When applied to a nonnegative symmetric n×n matrix with m nonzero entries and given as a weighted adjacency list, it runs in O(d(n+m)) time, where d is the depth of the recursion tree, which is at most the number of distinct nonzero entries
Original languageEnglish
Pages (from-to)151-165
JournalDiscrete Applied Mathematics
Volume222
DOIs
Publication statusPublished - May 2017

Keywords

  • Robinson (dis)similarity
  • Unit interval graph
  • Lex-BFS
  • Seriation
  • Partition refinement
  • Straight enumeration

Fingerprint Dive into the research topics of 'A Lex-BFS-based recognition algorithm for Robinsonian matrices'. Together they form a unique fingerprint.

  • Cite this