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

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