logo móvil
Contáctanos

Ordenando por reorganizaciones multi-corte

Autores: Bulteau, Laurent; Fertin, Guillaume; Jean, Géraldine; Komusiewicz, Christian

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro