On 4/25/06, Daniel Etzold <[EMAIL PROTECTED]
> wrote:
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
> >
--
-- 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
-~----------~----~----~----~------~----~------~--~---
