[scienze.unimo] Re: [scienze.unimo] Re: Verifica aciclicità in un grafo
- From: Emanuele Bardelli <51242@xxxxxxxx>
- To: scienze.unimo@xxxxxxxxxxxxx
- Date: Tue, 30 May 2006 10:30:15 +0200
Il giorno 29/mag/06, alle ore 23:00, Valerio Bigiani ha scritto:
Beh, tutti i cicli che stai facendo sono O(m) (la visita richiede O
(m) se usi liste di adiacenza, e per ogni arco puoi vedere se e'
nella foresta di visita con tempo costante se usi il vettore dei
padri, ripetuto per ogni arco). Se riesci a svolgere il problema in
meno di O(m), non puoi vedere tutti gli archi, il che, in base al
criterio 'a naso', significa che potresti trascurare proprio quello
che causa il ciclo.
Giusto, posso ricordarmi i nodi che non vengono inseriti nella
foresta, poi controllarmeli in un secondo momento, oppure potrei
controllare subito durante la visita, facendo un controllo sui tempi
di fine che avevamo inserito, dicendo che il nodo visitato non ha
ancora un tempo di fine (=infinito?) allora ho un ciclo, oppure un
arco trasversale.
Cavicchioli domani dimostrera' che si riesce a fare in tempo O(log
(log(log(log(m)))), CMQ la mia mente ridimensionata dall'alcol non
riesce a fare di meglio.
Per quanto riguarda i libri, prima di uploadarli aspetto che
qualcuno dalla Normale scannerizzi i capitoli sulle proiezioni del
loro libro.
Ciao,
Emanuele
Other related posts:
