For two disjoint paths each node of one path does not occur in the other path.
Mohammad Moghimi wrote: > how do you define disjoint path? > > On 4/24/06, *Daniel Etzold* <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> > wrote: > > > We have O(n^2) pairs. > A path from u to v can be found with a simple BFS in O(n+m) > When a path has been found we remove that path from the graph. > This has to be done k times. > Thus, searching for k paths is possible in O(k(n+m)). > > Doing this for each pair we get O(k(n^3+mn^2)) > > I think there are much more efficient algorithms for this problem. > > Regards, > Daniel > > Mohammad Moghimi wrote: > > > what is its time complexity? > > > > On 4/23/06, *Daniel Etzold* <[EMAIL PROTECTED] > <mailto:[EMAIL PROTECTED]> <mailto:[EMAIL PROTECTED] > <mailto:[EMAIL PROTECTED]>>> > > wrote: > > > > > > Hi, > > > > an equivalent defintion is: A graph is k-connected if for each > > pair of vertices u and v there exists k disjoint paths from u to > > v. > > > > Thus, a simple algorithm could be the following: > > for each pair <u,v> do > > search k disjoint paths from u to v > > od > > > > Regards, > > Daniel > > > > Mohammad Moghimi wrote: > > > > > Hi > > > Who can design a an algorithm for determining whether a > graph is > > > k-connected or not? > > > > > > ps: see definition of k-connectivity from > > > > http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 if you > > > want to know! > > > -- > > > -- Mohammad > > > do you C?!! > > > double m[] = { 9580842103863.650391 , 133470973390.236450, > 270}; > > > int main(){m[2]--?m[0]*=4,m[1]*=5,main():printf(m);} > > > > > > Don't attach in Microsoft (.DOC, .PPT) format > > > http://www.gnu.org/philosophy/no-word-attachments.html > > > > > > > > > > > > > > > > > > > > -- > > -- Mohammad > > do you C?!! > > double m[] = { 9580842103863.650391 , 133470973390.236450, 270}; > > int main(){m[2]--?m[0]*=4,m[1]*=5,main():printf(m);} > > > > Don't attach in Microsoft (.DOC, .PPT) format > > http://www.gnu.org/philosophy/no-word-attachments.html > > > > > > > > > > > -- > -- Mohammad > do you C?!! > double m[] = { 9580842103863.650391, 133470973390.236450, 270}; > int main(){m[2]--?m[0]*=4,m[1]*=5,main():printf(m);} > > Don't attach in Microsoft (.DOC, .PPT) format > http://www.gnu.org/philosophy/no-word-attachments.html > > --~--~---------~--~----~------------~-------~--~----~ 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.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
