A Lex-BFS-based recognition algorithm for Robinsonian matrices

Monique Laurent, M. Seminaroti

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

Robinsonian matrices arise in the classical seriation problem
and play an important role in many applications where unsorted sim-
ilarity (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-rst 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 of A.
Original languageEnglish
Title of host publicationProceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015)
EditorsPaschos Vangelis, Peter Widmayer
PublisherSpringer Verlag
Pages325-338
Number of pages14
Volume9079
Edition2015
ISBN (Print)9783319181721
DOIs
Publication statusPublished - 2015
Event9th Conference on on Algorithms and Complexity - Paris-Dauphine University, Paris, France
Duration: 20 May 201522 May 2015

Conference

Conference9th Conference on on Algorithms and Complexity
CountryFrance
CityParis
Period20/05/1522/05/15

Keywords

  • Robinson (dis)similarity unit interval graph Lex-BFS seriation partition renement straight enumeration
  • unit interval graph
  • Lex-BFS
  • seriation
  • partition renement
  • 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

    Laurent, M., & Seminaroti, M. (2015). A Lex-BFS-based recognition algorithm for Robinsonian matrices. In P. Vangelis, & P. Widmayer (Eds.), Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015) (2015 ed., Vol. 9079, pp. 325-338). Springer Verlag. https://doi.org/10.1007/978-3-319-18173-8