logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro