Français
Combinatorial and algorithmic properties of Robinsonian matrices
Multi angle
Authors : Laurent, Monique (Author of the conference)
CIRM (Publisher )
05C62 - Graph representations
05C85 - Graph algorithms
68R10 - Graph theory in connection with computer science
CIRM (Publisher )
Loading the player...
|
Abstract :
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.
MSC Codes : 05C62 - Graph representations
05C85 - Graph algorithms
68R10 - Graph theory in connection with computer science
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 14/09/17 Conference Date : 12/09/17 Subseries : Research talks arXiv category : Combinatorics ; Discrete Mathematics Mathematical Area(s) : Combinatorics ; Computer Science Format : MP4 (.mp4) - HD Video Time : 00:59:25 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2017-09-12_laurent.mp4 
|
Information on the Event
Event Title : 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)Event Organizers : Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan Carlos Dates : 11/09/17 - 15/09/17 Event Year : 2017 Event URL : http://conferences.cirm-math.fr/1660.html
Citation Data
DOI : 10.24350/CIRM.V.19221503Cite 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 |
See Also
- [Post-edited] The partially disjoint paths problem / Author of the conference Schrijver, Alexander.
- [Multi angle] Coloring graphs with forbidden induced paths / Author of the conference Chudnovsky, Maria.
- [Multi angle] Random hyperbolic graphs / Author of the conference Kiwi, Marcos.
- [Multi angle] Restricted types of matchings / Author of the conference Rautenbach, Dieter.
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
