On 4/24/06, Daniel Etzold <[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]>>
> 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
-~----------~----~----~----~------~----~------~--~---
