Temps d'exécution asymétrique nécessaire pour calculer la fermeture transitive d'un graphique? - langue agnostique, runtime, théorie, théorie des graphes

La fermeture transitive d'un graphe est définie e. g. ici: http://mathworld.wolfram.com/TransitiveClosure.html

Cela est facilement possible dans O (n ^ 3), où n est le nombre de sommets. Je me demandais si cela pouvait être fait dans le temps O (n ^ 2).

Réponses:

Nan. Je ne pense pas qu’il existe un O (n²) algorithme pour cela. Je pense que si un tel algorithme existait, vous pourriez résoudre tous les problèmes de paire de chemins les plus courts dans O (n²) aussi, ce qui n’est pas le cas. L’algorithme asymptotiquement le plus rapide auquel je peux penser est une implémentation de l’algorithme du chemin le plus court de Dijkstra avec un segment de Fibonacci (O (n²bûche n) dans des graphes peu denses).

Hmm. J'ai trouvé un algorithme qui calcule la fermeture transitive dans le temps d'exécution O (n ^ 2) EXPECTED.

Étant donné que cela:

Pouvez-vous proposer une fermeture / réduction transitive O (kn ^ 2 + m) algorithme, où k est le nombre de bords manquants / supplémentaires dans le transitif fermeture / réduction?

C’est toujours une question ouverte pour ceux qui pensent à ce genre de choses plus que nous, je dirais que je ne sais pas

(Mais si vous le résolvez et que vous voulez un doctorat, je sais cette algorithme.)