El cierre transitivo de un gráfico se define e. gramo. aquí: http://mathworld.wolfram.com/TransitiveClosure.html¿Tiempo de ejecución asimétrica necesario para calcular el cierre transitivo de un gráfico?
Es fácilmente posible en O (n^3), donde n es el número de vértices. Me preguntaba si se puede hacer a tiempo O (n^2).
No. No creo que haya un algoritmo O (n) para ello. Me gustaría esperar que si existiera un algoritmo así, pudieras resolver el problema de todos los pares de rutas más cortas en O (n) también, que no es el caso. El algoritmo asintóticamente más rápido que puedo pensar es una implementación del algoritmo de ruta más corta de Dijkstra con un montón de Fibonacci (O (n registro n) en gráficos no muy densas).
Hmm. Encontré un algoritmo que calcula el cierre transitivo en O (n^2) TIEMPO DE EJECUCIÓN ESPERADO.
Teniendo en cuenta que esto:
¿Se puede llegar a un O (kn^2 + m) cierre transitivo/reducción algoritmo, donde k es el número de desaparecidos bordes/adicionales en el cierre transitivo /¿reducción?
Todavía se considera una pregunta abierta por personas que piensan en este tipo de cosas más que nosotros, yo diría "No sé".
(Pero si lo resuelves y desea un doctorado, sé que algoritmo.)
con la que la distribución al azar? – jpalecek
ni idea. No quiero usarlo, porque no quiero ninguna aleatorización en mi algoritmo circundante. está aquí: http://www.springerlink.com/content/f511w61n62l17168/ – nes1983