Generalized Coloring of Permutations

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493166" target="_blank" >RIV/00216208:11320/24:10493166 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/24:00376080
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1s0M4xU6mL" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1s0M4xU6mL</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-024-01220-9" target="_blank" >10.1007/s00453-024-01220-9</a>

Result language
angličtina
Original language name
Generalized Coloring of Permutations
Original language description
A permutation p is a merge of a permutation q and a permutation r, if we can color the elements of p red and blue so that the red elements have the same relative order as q and the blue ones as r. We consider, for fixed hereditary permutation classes C and D, the complexity of determining whether a given permutation is a merge of an element of C with an element of D. We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of streaming recognizability of permutations via polynomially constructible nondeterministic automata, as well as a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich. As a consequence of the general results, we can provide nontrivial examples of tractable permutation merges involving commonly studied permutation classes, such as the class of layered permutations, the class of separable permutations, or the class of permutations avoiding a decreasing sequence of a given length. On the negative side, we obtain a general hardness result which implies, for example, that it is NP-complete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA21-32817S" target="_blank" >GA21-32817S: Algorithmic, structural and complexity aspects of geometric configurations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)