F Nous contacter

Multi angle

H 1 Combinatorial and algorithmic properties of Robinsonian matrices

Auteurs : Laurent, Monique (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterization by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem.

    Codes MSC :
    05C62 - Graph representations
    05C85 - Graph algorithms
    68R10 - Graph theory in connection with computer science

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 14/09/17
      Date de captation : 12/09/17
      Collection : Research talks
      Format : MP4
      Durée : 00:59:25
      Domaine : Combinatorics ; Computer Science
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2017-09-12_laurent.mp4

    Informations sur la rencontre

    Nom du congrès : IX Latin and American algorithms, graphs and optimization symposium (LAGOS 2017) / 9e symposium latino et americain des algorithmes, graphes et de l'optimisation (LAGOS 2017)
    Organisteurs Congrès : Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan Carlos
    Dates : 11/09/17 - 15/09/17
    Année de la rencontre : 2017
    URL Congrès : http://conferences.cirm-math.fr/1660.html

    Citation Data

    DOI : 10.24350/CIRM.V.19221503
    Cite this video as: Laurent, Monique (2017). Combinatorial and algorithmic properties of Robinsonian matrices. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19221503
    URI : http://dx.doi.org/10.24350/CIRM.V.19221503

    Voir aussi


    1. Laurent, M., & Seminaroti, M. (2017). Similarity-first search: a new algorithm with application to Robinsonian matrix recognition. SIAM Journal on Discrete Mathematics, 31(3), 1765-1800 - http://dx.doi.org/10.1137/16M1056791

    2. Laurent, M., Seminaroti, M., & Tanigawa, S.-I. (2017). A structural characterization for certifying Robinsonian matrices. The Electronic Journal of Combinatorics, 24(2), Paper P2.21 - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p21

    3. Laurent, M., & Seminaroti, M. (2015). A Lex-BFS-based recognition algorithm for Robinsonian matrices. In V.T. Paschos, & P. Widmayer (Eds.), Algorithms and complexity (pp. 325-338). Cham: Springer - http://dx.doi.org/10.1007/978-3-319-18173-8_24