Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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 k-letter graphs for a fixed k. However, explicit algorithms are available only for k = 2. 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. (C) 2020 Elsevier B.V. All rights reserved.
, ,