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]>> > 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 > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
