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

Fingerprint

Recognition Algorithm
Seriation
Interval Graphs
Breadth
Divide and conquer
Dissimilarity
Polynomial-time Algorithm
Non-negative
Distinct
Unit

Keywords

  • Robinson (dis)similarity unit interval graph Lex-BFS seriation partition renement straight enumeration
  • unit interval graph
  • Lex-BFS
  • seriation
  • partition renement
  • straight enumeration

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
Laurent, Monique ; Seminaroti, M. / A Lex-BFS-based recognition algorithm for Robinsonian matrices. Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015). editor / Paschos Vangelis ; Peter Widmayer. Vol. 9079 2015. ed. Springer Verlag, 2015. pp. 325-338
@inproceedings{7fc45990a64f44c3984732fba01d5967,
title = "A Lex-BFS-based recognition algorithm for Robinsonian matrices",
abstract = "Robinsonian matrices arise in the classical seriation problemand play an important role in many applications where unsorted sim-ilarity (or dissimilarity) information must be reordered. We present anew polynomial time algorithm to recognize Robinsonian matrices basedon a new characterization of Robinsonian matrices in terms of straightenumerations of unit interval graphs. The algorithm is simple and isbased essentially on lexicographic breadth-rst search (Lex-BFS), usinga divide-and-conquer strategy. When applied to a nonnegative symmetricn n matrix with m nonzero entries and given as a weighted adjacencylist, it runs in O(d(n + m)) time, where d is the depth of the recursiontree, which is at most the number of distinct nonzero entries of A.",
keywords = "Robinson (dis)similarity unit interval graph Lex-BFS seriation partition re nement straight enumeration, unit interval graph, Lex-BFS, seriation, partition re nement, straight enumeration",
author = "Monique Laurent and M. Seminaroti",
year = "2015",
doi = "10.1007/978-3-319-18173-8",
language = "English",
isbn = "9783319181721",
volume = "9079",
pages = "325--338",
editor = "Paschos Vangelis and Peter Widmayer",
booktitle = "Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015)",
publisher = "Springer Verlag",
address = "Germany",
edition = "2015",

}

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 edn, vol. 9079, Springer Verlag, pp. 325-338, 9th Conference on on Algorithms and Complexity, Paris, France, 20/05/15. https://doi.org/10.1007/978-3-319-18173-8

A Lex-BFS-based recognition algorithm for Robinsonian matrices. / Laurent, Monique; Seminaroti, M.

Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015). ed. / Paschos Vangelis; Peter Widmayer. Vol. 9079 2015. ed. Springer Verlag, 2015. p. 325-338.

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

TY - GEN

T1 - A Lex-BFS-based recognition algorithm for Robinsonian matrices

AU - Laurent, Monique

AU - Seminaroti, M.

PY - 2015

Y1 - 2015

N2 - Robinsonian matrices arise in the classical seriation problemand play an important role in many applications where unsorted sim-ilarity (or dissimilarity) information must be reordered. We present anew polynomial time algorithm to recognize Robinsonian matrices basedon a new characterization of Robinsonian matrices in terms of straightenumerations of unit interval graphs. The algorithm is simple and isbased essentially on lexicographic breadth-rst search (Lex-BFS), usinga divide-and-conquer strategy. When applied to a nonnegative symmetricn n matrix with m nonzero entries and given as a weighted adjacencylist, it runs in O(d(n + m)) time, where d is the depth of the recursiontree, which is at most the number of distinct nonzero entries of A.

AB - Robinsonian matrices arise in the classical seriation problemand play an important role in many applications where unsorted sim-ilarity (or dissimilarity) information must be reordered. We present anew polynomial time algorithm to recognize Robinsonian matrices basedon a new characterization of Robinsonian matrices in terms of straightenumerations of unit interval graphs. The algorithm is simple and isbased essentially on lexicographic breadth-rst search (Lex-BFS), usinga divide-and-conquer strategy. When applied to a nonnegative symmetricn n matrix with m nonzero entries and given as a weighted adjacencylist, it runs in O(d(n + m)) time, where d is the depth of the recursiontree, which is at most the number of distinct nonzero entries of A.

KW - Robinson (dis)similarity unit interval graph Lex-BFS seriation partition renement straight enumeration

KW - unit interval graph

KW - Lex-BFS

KW - seriation

KW - partition renement

KW - straight enumeration

U2 - 10.1007/978-3-319-18173-8

DO - 10.1007/978-3-319-18173-8

M3 - Conference contribution

SN - 9783319181721

VL - 9079

SP - 325

EP - 338

BT - Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015)

A2 - Vangelis, Paschos

A2 - Widmayer, Peter

PB - Springer Verlag

ER -

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