On 12/6/06, jackyy <[EMAIL PROTECTED]> wrote: > > Let G = (V,E) be a directed graph and s and t be two specific vertices > in G. We say > that s and t are k-connected if there are at least k edge-disjoint > paths between s and t. > Therefore, is there any algorithm to decide whether s and t are > k-connected? > Can you explain the algorithm in details? >
You can run Maximum flow algorithm on graph, with source as s and sink as t. Assign weight 1 to all edges. Maximum flow from s to t means "number of edge disjoint paths from s to t" http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow atamyrat > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---