Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< PREV    [ 1 2 ]
Re: Thanks _efer_ (response to post by _efer_) | Reply
topic :minimum number of vertices to disconnect the graph
quote :"This time we can't improve in the quadratic number of steps needed, because the first vertex may be in an optimum solution and by always considering it as the source we lose such a case. "

I think this can be optimised based on the result . for the first source(1st iteraiton) if the iteration gives a result of one vertice, well and good . else , we consider a second source(2nd iteration)...
We only have to continue if the best result so far > iteration no.

is my point valid?
Re: Thanks _efer_ (response to post by smartnut007) | Reply
Yes, I think you are right and here it is a proof: let's suppose the optimum solution is composed of vertices x_1, x_2, ..., x_k and let's suppose for the sake of contradiction that this solution can only be found at a step s > k + 1 (and contradict with your observation) then you must have that vertices 1, 2, ..., s - 1 are part of the solution (the ones you tried so far), otherwise you would have been able to find this solution earlier. Thus, you must have k >= s - 1 which implies k + 1 >= s, a contradiction.

Anyway this won't improve in the quadratic number of steps. Consider the case of a complete graph, in which you have an edge between every two vertices.
Re: Thanks _efer_ (response to post by aussie) | Reply
+1. Excellent article!
Re: Thanks _efer_ (response to post by _efer_) | Reply
hey, I was just curious what you generate the graphics with? It's very pretty!
Re: Thanks _efer_ (response to post by Larry) | Reply
See above, Corel Draw 12
Re: Thanks _efer_ (response to post by _efer_) | Reply
In section 2, I did not understand why in figure 9 the rightmost edge of the "after" network is marked with capacity 11 instead of 7 as we have to add 2 to each edge capacity.
Re: Thanks _efer_ (response to post by black.phoenix) | Reply
The text says "add 1", so what _efer_ probably meant when he said "take T = 2" is that he's going to multiply all capacities by 2, then add 1.
Re: Thanks _efer_ (response to post by _efer_) | Reply
One more question. That DFS given in the problem RookAttack would find as a result 2 instead of 3 returned by the BFS code for find_path(), wouldn't it? It checks for a new column if it wasn't visited, visit it and mark it as visited, terminating the function call. It does not try other columns anymore because it does not uncheck the visited array and returns as soon as a new match was found. So row 0 would match column 1, row 1 would match column 0 but row 2 would not match any columns, resulting in 2 rooks placed instead of the maximum of 3 rooks.

Maybe I understood the DFS code wrongly. Could anybody explain how it works?
<< PREV    [ 1 2 ]