2015-04-01
A Lex-BFS-based recognition algorithm for Robinsonian matrices
Publication
Publication
Presented at the
International Conference on Algorithms and Complexity, Paris
Robinsonian matrices arise in the classical seriation problem and play an important role
in many applications where unsorted similarity (or dissimilarity) information must be re-
ordered. 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 non-
negative 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.
Additional Metadata | |
---|---|
, , , , , | |
Springer | |
V. Paschos , P. Widmayer | |
Mixed-Integer Nonlinear Optimization | |
International Conference on Algorithms and Complexity | |
Organisation | Networks and Optimization |
Laurent, M., & Seminaroti, M. (2015). A Lex-BFS-based recognition algorithm for Robinsonian matrices. In V. Paschos & P. Widmayer (Eds.), Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings (pp. 325–338). Springer. |