Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
Alecu, Bogdan; Lozin, Vadim; Zamaraev, Viktor; de Werra, Dominique
2018

Abstract

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.

Details

Title Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
Author(s) Alecu, Bogdan ; Lozin, Vadim ; Zamaraev, Viktor ; de Werra, Dominique
Published in Combinatorial Algorithms, Iwoca 2017
Series Lecture Notes in Computer Science
Volume 10765
Pages 195-205
Conference 28th International Workshop on Combinational Algorithms (IWOCA), Newcastle, AUSTRALIA, Jul 17-21, 2017
Date 2018-01-01
Publisher Cham, SPRINGER INTERNATIONAL PUBLISHING AG
ISSN 0302-9743
1611-3349
ISBN 978-3-319-78825-8
978-3-319-78824-1
Keywords
DOI https://doi.org/10.1007/978-3-319-78825-8_16
Other identifier(s) View record in Web of Science
Laboratories ROSE
Record Appears in Scientific production and competences > SB - School of Basic Sciences > SB Archives > ROSE - Chair of Operations Research SE
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Conference Papers
Work produced at EPFL
Published
Record creation date 2018-12-13