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)

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

Organizer(s) Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan Carlos

Date(s) 11/09/2017 - 15/09/2017

linked URL http://conferences.cirm-math.fr/1660.html

00:00:00 / 00:00:00

3 5

Combinatorial and algorithmic properties of Robinsonian matrices

By Monique Laurent

Also appears in collection : Exposés de recherche

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.

Information about the video

Date of recording 12/09/2017
Date of publication 14/09/2017
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Guillaume Hennenfent
Format MP4

Citation data

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

Domain(s)

Bibliography

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

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

54:56

published on September 14, 2017

Coloring graphs with forbidden induced paths

By Maria Chudnovsky

54:35

published on September 14, 2017

The partially disjoint paths problem

By Alexander Schrijver

59:25

published on September 14, 2017

Combinatorial and algorithmic properties of Robinsonian matrices

By Monique Laurent

53:47

published on September 14, 2017

Random hyperbolic graphs

By Marcos Kiwi

01:06:10

published on September 14, 2017

Restricted types of matchings

By Dieter Rautenbach

Copyright Carmin.tv 2024

Give feedback