Construcción de un árbol evolutivo y evolución del gráfico de camino-ciclo a lo largo de él
Autores: Gorbunov, Konstantin; Lyubetsky, Vassily
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Construcción de un árbol evolutivo y evolución del gráfico de camino-ciclo a lo largo de él
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
árbol evolutivo
Estructuras
Algoritmo
Incrustación
Red
Complejidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
El documento resuelve el problema de construir un árbol evolutivo y la evolución de estructuras a lo largo de él. Este problema ha sido planteado durante mucho tiempo y ha sido investigado extensamente; se formula y se discute a continuación. Como resultado, construimos un algoritmo exacto de tiempo cúbico que produce un árbol con el costo mínimo de inserción en él y de insertarlo en una red dada (Teorema 1). Construimos un algoritmo que produce una inserción mínima de un árbol en una red, teniendo en cuenta la clasificación lineal incompleta; el algoritmo depende linealmente del número de nodos en la red y es exacto si el costo de clasificación no es menor que la suma del costo de duplicación y el costo de pérdida (Teorema 3). Construimos un algoritmo aproximadamente cuadrático exacto que, para costos arbitrarios de operaciones, resuelve el problema de reconstrucción de estructuras dadas en cualquier árbol de dos estrellas (Teorema 4). Construimos un algoritmo exacto que reduce el problema de reconstrucción de estructuras dadas en cualquier estrella a una secuencia de longitud logarítmica de problemas SAT, cada uno de ellos de tamaño aproximadamente cuadrático (Teorema 5). Los teoremas tienen pruebas rigurosas y completas de la corrección y complejidad de los algoritmos, y están acompañados de ejemplos numéricos y numerosas ilustraciones explicativas, incluidos diagramas de flujo.
Descripción
El documento resuelve el problema de construir un árbol evolutivo y la evolución de estructuras a lo largo de él. Este problema ha sido planteado durante mucho tiempo y ha sido investigado extensamente; se formula y se discute a continuación. Como resultado, construimos un algoritmo exacto de tiempo cúbico que produce un árbol con el costo mínimo de inserción en él y de insertarlo en una red dada (Teorema 1). Construimos un algoritmo que produce una inserción mínima de un árbol en una red, teniendo en cuenta la clasificación lineal incompleta; el algoritmo depende linealmente del número de nodos en la red y es exacto si el costo de clasificación no es menor que la suma del costo de duplicación y el costo de pérdida (Teorema 3). Construimos un algoritmo aproximadamente cuadrático exacto que, para costos arbitrarios de operaciones, resuelve el problema de reconstrucción de estructuras dadas en cualquier árbol de dos estrellas (Teorema 4). Construimos un algoritmo exacto que reduce el problema de reconstrucción de estructuras dadas en cualquier estrella a una secuencia de longitud logarítmica de problemas SAT, cada uno de ellos de tamaño aproximadamente cuadrático (Teorema 5). Los teoremas tienen pruebas rigurosas y completas de la corrección y complejidad de los algoritmos, y están acompañados de ejemplos numéricos y numerosas ilustraciones explicativas, incluidos diagramas de flujo.