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)

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

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

URL associée http://conferences.cirm-math.fr/1660.html

00:00:00 / 00:00:00

3 5

Combinatorial and algorithmic properties of Robinsonian matrices

De Monique Laurent

Apparaît également dans la 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.

Informations sur la vidéo

Date de captation 12/09/2017
Date de publication 14/09/2017
Institut CIRM
Licence CC BY NC ND
Langue Anglais
Audience Chercheurs
Réalisateur(s) Guillaume Hennenfent
Format MP4

Données de citation

DOI 10.24350/CIRM.V.19221503
Citer cette vidéo 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

Domaine(s)

Bibliographie

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

Codes MSC

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow

Toutes les vidéos de la collection

54:56

publiée le 14 septembre 2017

Coloring graphs with forbidden induced paths

De Maria Chudnovsky

54:35

publiée le 14 septembre 2017

The partially disjoint paths problem

De Alexander Schrijver

59:25

publiée le 14 septembre 2017

Combinatorial and algorithmic properties of Robinsonian matrices

De Monique Laurent

53:47

publiée le 14 septembre 2017

Random hyperbolic graphs

De Marcos Kiwi

01:06:10

publiée le 14 septembre 2017

Restricted types of matchings

De Dieter Rautenbach

Copyright Carmin.tv 2024

Donner son avis