A Lex-BFS-based recognition algorithm for Robinsonian matrices

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 … Read more

The Quadratic Assignment Problem is Easy for Robinsonian Matrices

We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form QAP(A,B), by showing that the identity permutation is optimal when A and B are respectively a Robinson similarity and dissimilarity matrix and one of A or B is a Toeplitz matrix. A Robinson (dis)similarity matrix is a symmetric matrix whose … Read more