La chiusura transitiva di un grafico è definita e. g. qui: http://mathworld.wolfram.com/TransitiveClosure.htmlTempo di corsa asimmetrico necessario per calcolare la chiusura transitiva di un grafico?
È facilmente possibile in O (n^3), dove n è il numero di vertici. Mi stavo chiedendo se può essere fatto nel tempo O (n^2).
No. Non penso ci sia un algoritmo O (n) per questo. Mi aspetterei se esistesse un tale algoritmo, potreste risolvere anche il problema di tutti i percorsi più corti in O (n), il che non è il caso. L'algoritmo asintoticamente più veloce che riesco a pensare è un'implementazione dell'algoritmo del percorso più breve di Dijkstra con un heap di Fibonacci (O (n log n) in grafici non molto densi).
Hmm. Ho trovato un algoritmo che calcola la chiusura transitiva in O (n^2) tempo di esecuzione ATTESA.
Dato che questo:
Puoi venire con un O (kn^2 + m) chiusura transitiva/riduzione algoritmo, dove k è il numero della mancanza/bordi supplementari la chiusura transitiva /riduzione?
È ancora considerata una domanda aperta da persone che pensano a questo genere di cose più di noi, direi "Non so".
(Ma se si risolve e si desidera un dottorato di ricerca, lo so che algoritmo.)
con cui distribuzione casuale? – jpalecek
nessuna idea. Non voglio usarlo, perché non voglio alcuna randomizzazione nel mio algoritmo circostante. è qui: http://www.springerlink.com/content/f511w61n62l17168/ – nes1983