¿Hay una estructura de datos para DAG que admita ediciones eficientes?

Estoy buscando una estructura de datos que almacenará cualquier DAG, pero puede detectar de manera eficiente (es decir, sub-linealmente en el número de bordes/vértices) si agregar un borde crearía un ciclo (y así evitar que rompa el invariante acíclico). ¿Alguien sabe de tal cosa?¿Hay una estructura de datos para DAG que admita ediciones eficientes?

Gracias!

Fuente

2011-10-25 copumpkin

Este artículo, [Algoritmos más rápidos para Topological incremental Pedidos] (http://www.cs.princeton.edu/~sssix/papers/dto-conf.pdf), reclama un ** amortizado ** O (m^1/2) por adición de arco. No estoy seguro de si eso es lo suficientemente bueno, o si es posible un peor caso enlazado. No he leído más allá de la introducción. – Crosbie

Puede mantener una estructura de datos sobre el gráfico transitive closure. Luego, verifica si agregar un borde causa ciclos se realiza en tiempo constante; si desea agregar edge (i, j), verifique si ya hay un camino de j a i. Sin embargo, la actualización de la estructura de datos podría ser más costosa en general (véase, por ejemplo, La Poutré and van Leeuwen).

Fuente

2011-12-26 11:30:17 mitchus

¿Hay una estructura de datos para DAG que admita ediciones eficientes?

Respuesta

Cuestiones relacionadas