### Abstract

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

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 | France |

City | Paris |

Period | 20/05/15 → 22/05/15 |

### Fingerprint

### 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

*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

}

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

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