Letter graphs and geometric grid classes of permutations: characterization and recognition

DOI10.1007/978-3-319-78825-8_16OpenAlexW2798714101MaRDI QIDQ5915647

Victor Zamaraev, Bogdan Alecu, Dominique de Werra, Vadim V. Lozin

Publication date: 15 June 2018

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/122194/1/WRAP-Letter-graphs-geometric-grid-classes-permutations-Lozin-2020.pdf

zbMATH Keywords

polynomial-time algorithmrecognition of 3-letter graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Letter Graphs and Geometric Grid Classes of Permutations, Labelled well-quasi-order for permutation classes, Letter graphs and modular decomposition