at the and what is the solution? is this problem very classic? Did anyone find any solution to this problem?On 4/27/06, Karthik Singaram L
[EMAIL PROTECTED] wrote:yes u r rite. I was trying to force the usage of BFS but it looks to perform very very bad
-- -- Mohammaddo you C?!! double m[] =
finding all the paths is crazy)) in worst case you get about n! paths.
But even having all the paths, it is not clear how you can find out if
there are k of them sharing no vertex. It is sort of set covering
problem that is not very easy by itself.
I dont think max flow would work, because a max flow of 'k' will
guarantee atleast k edges and not vertices. It is easy to come up
with a case where removal of just one vertex will disconnect a graph
with max flow of 'k'.
On the other hand, I think the BFS would work pretty well, just
ensuring
hard to undestand what you mean by removing vertices in the path and
not
edges. How can you remove a vertex without removing all its edges ?
When i talked of maximum flow i of course ment that you also need put
restriction on vertexes too. All edges and vertexes have unit capacity.
Well .. I actually meant vertices as well as its edges ... not the
other way around. Just a typo.
Interesting ... how do you put restriction on vertices ? I havent
heard of a max flow like it.
-Dhyanesh
On 4/25/06, forest [EMAIL PROTECTED] wrote:
hard to undestand what you mean by removing
there is an example of BFS fail:
- - - 2 6 - - - -- 7- - - - -
S / -- - - - - - /F
- - - 3- - - - 4 - -- - - 5 - -- - - -
going form S to F. k = 2. BFS finds path S37F, as it is shortest.
After removing this path there is no other path from S to F. But
Hmmm.. Interesting
Just in case someone does want to use BFS and does not really care
about the time complexity,
then you could do BFS to get all the Paths ( do not remove them as
soon as you get them )
For example in the graph in the previous discussion, BFS would give
S37F, S345F and
of course the time complexity could be substantially reduced using the
flow model of the problem.l\
On 4/26/06, Karthik Singaram L [EMAIL PROTECTED] wrote:
Hmmm.. Interesting
Just in case someone does want to use BFS and does not really care
about the time complexity,
then you could do BFS
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
I believe with this condition we have a k connected graph but why it is essential?On 4/25/06, Daniel Etzold [EMAIL PROTECTED]
wrote:For two disjoint paths each node of one pathdoes not occur in the other path.
Mohammad Moghimi wrote: how do you define disjoint path? On 4/24/06, *Daniel Etzold*
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
what is its time complexity?On 4/23/06, Daniel Etzold [EMAIL PROTECTED] wrote:
Hi,an equivalent defintion is: A graph is k-connected if for eachpair of vertices u and v there exists k disjoint paths from u tov.Thus, a simple algorithm could be the following:for each pair u,v do
search k disjoint
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
13 matches
Mail list logo
