Quale sarebbe il miglior algoritmo per trovare localbridge (k) in Graph? Un ponte locale di grado k è un bordo la cui rimozione farebbe ingrandire la distanza più breve tra i suoi due punti finali almeno a k.LocalBridge of degree k nel grafico
Wikipedia: http://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge
Eseguire un algoritmo all-percorso più breve-costi, come l'algoritmo Floyd-Warshall, ma in cui si utilizza tuple (d1,d2) per le distanze, invece dei numeri reali tipici d:
d1 è la lunghezza del percorso più breved2 è la lunghezza del secondo più breve percorsoQuesta modifica all'algoritmo di Floyd-Warshall dovrebbe essere semplice.
Quando si è fatto in esecuzione l'algoritmo all-breve-path-costi, i bordi sono localbridge(k) i bordi e = {u, v} tale che la distanza tra il (1,d2)u e v soddisfa d2 >= k.
È [abbastanza buono l'algoritmo di Floyd-Warshall] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)? – anatolyg
Sei interessato a trovare tutti i ponti locali nel grafico? Forse hai avuto uno (o due) nodi specifici in mente. – phs