Ordenando por reorganizaciones multi-corte
Autores: Bulteau, Laurent; Fertin, Guillaume; Jean, Géraldine; Komusiewicz, Christian
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Ordenando por reorganizaciones multi-corte
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Cadena
Reorganizaciones
Problema
Complejidad
Algorítmico
Permutaciones
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
Una de una cadena es una cadena obtenida de por una operación llamada , que consiste en (1) cortar en un número dado de lugares en , haciendo la cadena concatenada , donde y son posiblemente vacíos, y (2) reorganizar los de manera que se obtenga , siendo una permutación en que satisface y . Dadas dos cadenas y construidas sobre el mismo multiconjunto de caracteres de un alfabeto , el problema de () pregunta si un número dado de reorganizaciones de corte de - son suficientes para transformar en . El problema generaliza varios problemas clásicos de reorganizaciones genómicas, como y . También puede modelar , un fenómeno recientemente descubierto que consiste en reorganizaciones simultáneas masivas. En este documento, estudiamos el problema desde un punto de vista de complejidad algorítmica. Más precisamente, investigamos su complejidad clásica y parametrizada, así como su aproximabilidad, en el caso general o cuando y son permutaciones.
Descripción
Una de una cadena es una cadena obtenida de por una operación llamada , que consiste en (1) cortar en un número dado de lugares en , haciendo la cadena concatenada , donde y son posiblemente vacíos, y (2) reorganizar los de manera que se obtenga , siendo una permutación en que satisface y . Dadas dos cadenas y construidas sobre el mismo multiconjunto de caracteres de un alfabeto , el problema de () pregunta si un número dado de reorganizaciones de corte de - son suficientes para transformar en . El problema generaliza varios problemas clásicos de reorganizaciones genómicas, como y . También puede modelar , un fenómeno recientemente descubierto que consiste en reorganizaciones simultáneas masivas. En este documento, estudiamos el problema desde un punto de vista de complejidad algorítmica. Más precisamente, investigamos su complejidad clásica y parametrizada, así como su aproximabilidad, en el caso general o cuando y son permutaciones.