A Lex-BFS-based recognition algorithm for Robinsonian matrices

Monique Laurent; M. Seminaroti

doi:10.1007/978-3-319-18173-8

A Lex-BFS-based recognition algorithm for Robinsonian matrices

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-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 language	English
Title of host publication	Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015)
Editors	Paschos Vangelis, Peter Widmayer
Publisher	Springer Verlag
Pages	325-338
Number of pages	14
Volume	9079
Edition	2015
ISBN (Print)	9783319181721
DOIs	https://doi.org/10.1007/978-3-319-18173-8
Publication status	Published - 2015
Event	9th Conference on on Algorithms and Complexity - Paris-Dauphine University, Paris, France Duration: 20 May 2015 → 22 May 2015

Conference

Conference	9th Conference on on Algorithms and Complexity
Country/Territory	France
City	Paris
Period	20/05/15 → 22/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

Access to Document

10.1007/978-3-319-18173-8

Cite this

@inproceedings{7fc45990a64f44c3984732fba01d5967,

title = "A Lex-BFS-based recognition algorithm for Robinsonian matrices",

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.",

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",

note = "9th Conference on on Algorithms and Complexity ; Conference date: 20-05-2015 Through 22-05-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 proceeding › Conference contribution › Scientific › peer-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 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.

AB - 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.

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

T2 - 9th Conference on on Algorithms and Complexity

Y2 - 20 May 2015 through 22 May 2015

ER -

A Lex-BFS-based recognition algorithm for Robinsonian matrices

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this