Flusso massimo nei grafici dinamici

Sto cercando un algoritmo veloce per calcolare il flusso massimo nei grafici dinamici (aggiunta/eliminazione di nodi con bordi correlati al grafico). abbiamo il flusso massimo in G ora nuovo nodo aggiunto/eliminato con bordi correlati, non mi piace ricalcolare il flusso massimo per il nuovo grafico, infatti, voglio utilizzare i precedenti risultati disponibili per questo grafico.Flusso massimo nei grafici dinamici

Qualsiasi preelaborazione che non è molto tempo/memoria di consumo è appropriata.

L'idea più semplice è il ricalcolo del flusso.

Un'altra semplice idea è come questo, salvare tutti i percorsi che aumentano il quale utilizzati nel precedente calcolo MaxFlow, ora per l'aggiunta di vertice v, possiamo trovare percorsi semplici (grafico capacità aggiornato da passo precedente) che partono dalla sorgente, va a v poi va a destinazione, ma il problema è che questo percorso dovrebbe essere semplice, non potrei trovare meglio di O (n * E) per questo caso. (se era solo un percorso o i percorsi erano disgiunti, questo può essere fatto in O (n + E), ma non è così).

Anche per la rimozione del nodo sopra l'idea non funziona.

Anche la mia domanda non è correlata a another question which looks on dynamic edges adding/removing.

fonte

2012-01-26 Saeed Amiri

In che modo la domanda non è correlata al link che hai fornito? Mi sembra azzeccato. –

@KeithRandall, la mia domanda riguarda l'aggiunta dell'eliminazione del vertice, ma quella domanda riguardava i bordi, infatti con un vertice probabilmente aggiungerai i bordi 'n', quindi il caso del vertice è più complicato del caso limite, ad esempio posso avere qualche intuizione con bordi, ma la mia migliore soluzione per i vertici non è una buona soluzione. –

@Charles, descriveresti perché hai rimosso il tag max-flow? Ho aggiunto questo tag a SO perché è utile. specialmente nelle ricercheI bordi –

Ho fatto questa domanda in CSTheory.StackExchange, per l'aggiunta di nodo Ho discusso con altri che ho trovato che il ricalcolo è più veloce di altri algoritmi noti, perché il ricalcolo gira su un grafico semi-sparse (grafico residuo) quindi è abbastanza veloce anche per rimuovere il nodo, c'era una buona risposta, dividendo il nodo (che vuole essere rimosso) in due set, v_in e v_out e il calcolo del flusso sul grafico residuo da v_in a v_out, e di nuovo il calcolo del flusso nel grafico residuo da v_in a v_out con l'aggiunta di un bordo infinito tra origine e destinazione. (e infine confrontando la loro differenza e aggiornando il grafico residuo). È possibile visualizzare la Q/A correlata e le discussioni in Incremental Maximum Flow in Dynamic graphs.

fonte

2012-02-25 15:58:45

Per aggiungere dinamicamente un vertice v ed i suoi bordi associati E:

1) Aggiungere v da solo al grafico. Poiché non ha bordi, non può influenzare il flusso massimo.

2) Aggiungere i bordi associato E al grafico, uno alla volta, utilizzando l'algoritmo this question

fare il contrario per eliminazione di un vertice e la sua bordi associato.

fonte

2012-01-27 01:21:36

-1 Conoscete l'ordine dell'algoritmo? è più di O (E) per ogni spigolo infatti non è buono (il mio algoritmo è più semplice e veloce), anche questo (quello che hai offerto) non copre la cancellazione del nodo. –

Per aggiungere Vertex v, utilizzare il vecchio Flow f e calcolare il grafico residuo, quindi ottenere un percorso di incremento da DFS OutDeg (v) volte.

Per rimuovere un Vertex v - calcolare tutto il flusso che lascia v, dire la somma del flusso che lascia v è a, quindi mentre (a> 0) trovare un percorso P da s a t che sta andando a v, e ridurre f (P) dal flusso e da a.

Penso che dovrebbe aiutare ... im più sicura sull'aggiunta poi sulla rimozione, in modo id amano farsi corretto nei commenti :)

fonte

2012-02-12 00:01:23

Buona offerta ma il tuo approccio per l'aggiunta del vertice prende O (n * E) nel peggiore dei casi, Anche l'opzione di rimozione prende O (n * E) Inoltre non penso sia giusto, ma il tuo approccio di aggiunta è più semplice del mio. –

Non penso che tu possa fare qualcosa di meglio allora ... sei sicuro che ci sia un modo migliore? notare che outdeg (v) non è probabile che sia così alto nella maggior parte dei grafici, quindi il suo caso dovrebbe essere eseguito in O (E) ... –

Nessuna media non dovrebbe essere O (E), in media (con grafici casuali) tu avrà gradi intorno n/2 per i nuovi vertici. ma attualmente penso che il tuo algoritmo abbia qualche bug, non è essenzialmente il calcolo del tempo di laurea (v), potrebbe essere necessario più di questo (nei casi in cui attraversi un nuovo margine aggiunto più di una volta). Inoltre, non penso che ci sia un algoritmo semplice, ma chiedi qui per vedere se qualcuno ha una buona idea? –

Flusso massimo nei grafici dinamici

risposta

Problemi correlati