1. casa
  2. Domanda e risposta
  3. Esiste una struttura dati per i DAG che supporta modifiche efficienti?

Esiste una struttura dati per i DAG che supporta modifiche efficienti?

2011-10-25 10 views
9

Sto cercando una struttura dati che memorizzerà qualsiasi DAG, ma può efficientemente (cioè, in modo sub-lineare nel numero di fronti/vertici) rilevare se l'aggiunta di un bordo creerebbe un ciclo (e quindi impedirà di rompere il invariante aciclico). Qualcuno sa di una cosa del genere?Esiste una struttura dati per i DAG che supporta modifiche efficienti?

Grazie!

fonte

2011-10-25 copumpkin

+4

Questo documento, [Algoritmi più veloci per topologico incrementale Ordinamento] (http://www.cs.princeton.edu/~sssix/papers/dto-conf.pdf), rivendica un ** ammortizzato ** O (m^1/2) per aggiunta di arco. Non sono sicuro se sia abbastanza buono, o se è possibile un limite nel caso peggiore. Non ho letto oltre l'introduzione. – Crosbie

risposta

1

È possibile mantenere una struttura dati sul grafico transitive closure. Quindi verificare se l'aggiunta di un bordo provoca cicli eseguiti in tempo costante; se vuoi aggiungere edge (i, j), controlla se esiste già un percorso da j a i. Tuttavia, l'aggiornamento della struttura dati potrebbe essere più costoso in generale (ad esempio, La Poutré and van Leeuwen).

fonte

2011-12-26 11:30:17 mitchus

Problemi correlati

 Problemi correlati