Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
2018
Résumé
In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. We also present the first constructive polynomial-time algorithm for the recognition of 3-letter graphs.
Détails
Titre
Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
Auteur(s)
Alecu, Bogdan ; Lozin, Vadim ; Zamaraev, Viktor ; de Werra, Dominique
Publié dans
Combinatorial Algorithms, Iwoca 2017
Série
Lecture Notes in Computer Science
Volume
10765
Pages
195-205
Présenté à
28th International Workshop on Combinational Algorithms (IWOCA), Newcastle, AUSTRALIA, Jul 17-21, 2017
Date
2018-01-01
Editeur
Cham, SPRINGER INTERNATIONAL PUBLISHING AG
ISSN
0302-9743
1611-3349
1611-3349
ISBN
978-3-319-78825-8
978-3-319-78824-1
978-3-319-78824-1
Mots-clés (libres)
Autres identifiant(s)
Afficher la publication dans Web of Science
Laboratoires
ROSE
Le document apparaît dans
Production scientifique et compétences > SB - Faculté des sciences de base > SB Archives > ROSE - Chaire de recherche opérationnelle SE
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Papiers de conférence
Travail produit à l'EPFL
Publié
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Papiers de conférence
Travail produit à l'EPFL
Publié
Date de création de la notice
2018-12-13