Alecu, Bogdan, Lozin, Vadim V., Werra, Dominique de and Zamaraev, Viktor (2020) Letter graphs and geometric grid classes of permutations : characterization and recognition. Discrete Applied Mathematics, 283 . pp. 482-494. doi:10.1016/j.dam.2020.01.038 ISSN 0166-218X.

Preview

PDF WRAP-Letter-graphs-geometric-grid-classes-permutations-Lozin-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (869Kb) | Preview

Request Changes to record.

Abstract

In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is well-quasi-orderability, implying, in a non-constructive way, a polynomial-time recognition of geometric grid classes of permutations and -letter graphs for a fixed . However, explicit algorithms are available only for . In this paper, we present the first explicit polynomial-time algorithm for the recognition of 3-letter graphs over a cyclic decoder. It is based on a structural characterization of graphs in this class

Item Type:	Journal Article
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	Discrete Applied Mathematics
Publisher:	Elsevier Science Ltd.
ISSN:	0166-218X
Official Date:	15 September 2020
Dates:	Date Event 15 September 2020 Published 14 February 2020 Available 30 January 2020 Accepted
Volume:	283
Page Range:	pp. 482-494
DOI:	10.1016/j.dam.2020.01.038
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	19 March 2020
Date of first compliant Open Access:	14 February 2021

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads