Muchos algoritmos de flujo máximo que comúnmente veo implementados, el algoritmo de Dinic, el relé de empuje y otros, pueden mejorar su costo de tiempo asintótico a través del uso de árboles dinámicos (también conocidos como árboles de corte de enlace).
- Push reetiquetado se ejecuta normalmente en u u , pero con árboles dinámicos
- El algoritmo de Dinic se ejecuta en , pero con árboles dinámicos
Sin embargo, las implementaciones prácticas de algoritmos de flujo máximo en la mayoría de las bibliotecas no parecen hacer uso de esta estructura de datos. ¿Se utilizan árboles dinámicos en la práctica para el cálculo del flujo máximo? ¿O llevan demasiados gastos generales para ser útiles para los problemas del mundo real?
¿Hay otros dominios problemáticos en los que se usan árboles de corte de enlace?
Esta pregunta está relacionada con una pregunta que hice en teoría: ¿Son prácticos algunos de los algoritmos de flujo máximo de última generación?
fuente
Respuestas:
Hay un documento titulado " Árboles dinámicos en la práctica " que revisa la implementación práctica.
Las otras categorías en las que el árbol Link-Cut podría usarse de manera eficiente se encuentran en la indexación de bases de datos . Puede encontrar esto en el libro " Técnicas de índice de base de datos ".
fuente
Este artículo encuentra al final que un árbol de corte de enlace (LC) supera a los árboles de compresión de rastrillo (RC) para el algoritmo de flujo máximo Sleator / Tarjan utilizando un generador de gráficos aleatorios Dimacs estándar.
El documento se centra en la propagación del cambio como una aplicación de los árboles dinámicos. por ejemplo, la propagación de cambios es similar a la forma en que las celdas de hoja de cálculo de Excel tienen que ser recalculadas en los cambios a algunas celdas en función de las dependencias de celda / fórmula. Los autores publicaron su código como una biblioteca abierta.
Un análisis experimental de la propagación del cambio en árboles dinámicos Acar, Blelloch, Vittes
fuente