I believe that the Guan-Williams algorithm for finding the minimum-diameter spanning tree has a mistake. Here is a test case that breaks it.
Code: Select all
11 vertices, 10 edges:
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 9
9 10
Moderator: Board moderators
Code: Select all
11 vertices, 10 edges:
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 9
9 10
I've implemented this algorithm and it returns 8 on your test case. I didn't assume at each edge splitting that if one removes the inserted vertex the tree will have d(T)-1 diameter, i simply recalculate the diameter for the tree on each edge splitting. I've tested on a lot of random test cases and made a validator the check if the result outputted is valid (i also output a tree and i check to see if this tree has the diameter i say) and i've also gotten max points in the Romanian contest you were talking about, but still i get WA here at UVA...Abednego wrote:If you read the algorithm description carefully, it will try BFS(10), find that it gives a minimum diameter BFS tree, and then try to split edge 9-10, which will cause it to return 7. I e-mailed the authors, but got no reply yet. It's also unfortunate that they give no formal proof of correctness - they simply state some claims and pretend they are obvious.
The algorithm we are talking about is the one from this page:
http://www.cs.utexas.edu/users/yguan/pa ... node2.html
Thanks to everyone who sent clarifications during the contest.
First, a disclaimer: I didn't even attempt to implement the algorithm, but my point of view is that the algo is correct , like domino implemented it,Abednego wrote:If you read the algorithm description carefully, it will try BFS(10), find that it gives a minimum diameter BFS tree, and then try to split edge 9-10, which will cause it to return 7. I e-mailed the authors, but got no reply yet. It's also unfortunate that they give no formal proof of correctness - they simply state some claims and pretend they are obvious.
The algorithm we are talking about is the one from this page:
http://www.cs.utexas.edu/users/yguan/pa ... node2.html
Thanks to everyone who sent clarifications during the contest.
Mmm, well, this case would be equivalent to the previous one *IF* we could prove that splitting the edge in T that links v (which is defined to be one of the two midpoints of P) to the subtree containing its deepest child would make the diameter equal to d+1. But I am not able to prove it, because nothing tells us that the path P is the shortest path between its extremities in the original graph.nnahas wrote:[
Case 2: The minimum diameter spanning tree T has an even diameter d(meaning the longest path has an even number of vertices.)
First , my remark that the code would be very easy to implement referred to the computation of the minimum diameter, not the actual tree.nnahas wrote: We still have to prove that the existence of T implies the existence of a BFS tree rooted at v having the same property as T (namely that all its deepest nodes are the descendants of the same child of v.)
I'll leave that to a later message. Stay Tuned
I think you misinterpret what the Guan Williams algorithm says. When they say odd diameter, they mean an odd number of vertices on the longest path, not the sum of edge costs along the path. so here the diameter they find is 9, and there's no need for edge splitting.Abednego wrote:If you are using the algorithm by Yuqiang Guan and Kenneth Williams, you will get a wrong answer. The same goes for the official solution to a similar problem from a Romanian contest.
I believe that the Guan-Williams algorithm for finding the minimum-diameter spanning tree has a mistake. Here is a test case that breaks it.The correct answer is 8, not 7.Code: Select all
11 vertices, 10 edges: 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 4 9 9 10
Well now I do have my own implementation but I'm getting WA. I'll try to fix it.Cosmin.ro wrote:I'm the problemsetter of a similar problem in the Romanian contest abednego is talking about. The official solution I used in that contest outputs 8 not 7 on the example given above, I've implemented the algorithm sugested by the link mentioned before. Also I wanted to add that in the Romanian contest it was intended for a solution to get maximum points only if it implemented a O(n^3) or lower algo, in fact Domino's solution was fine tuned O(m*m) and it got full marks. My O(n^3) solution is similar to nnhas ideeas, and if instead of computing the distance matrix with Roy Floyd we use n breadth first searches then we get a O(n*m) algorithm.
nnhas if you need to see a sourcecode I can send it to you but my implementation is in pascal, also my problem asked for the tree not only the diameter so I find the tree as well.
Code: Select all
25 182
0 1
0 3
0 4
0 6
0 7
0 9
0 10
0 12
0 16
0 19
0 21
0 22
0 23
0 24
1 2
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 17
1 19
1 20
2 3
2 5
2 6
2 8
2 10
2 11
2 14
2 16
2 17
2 20
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 19
3 20
3 21
3 22
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 15
4 19
4 20
4 22
4 23
5 7
5 8
5 11
5 12
5 13
5 15
5 16
5 17
5 19
5 20
5 23
5 24
6 8
6 10
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 20
6 24
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 17
7 21
7 22
7 23
7 24
8 10
8 11
8 14
8 15
8 17
8 18
8 19
8 20
8 21
8 23
8 24
9 11
9 13
9 15
9 16
9 19
9 21
9 22
9 23
9 24
10 11
10 13
10 14
10 15
10 16
10 17
10 18
10 19
10 22
10 24
11 13
11 16
11 17
11 18
11 19
11 21
11 22
11 23
11 24
12 13
12 14
12 17
12 21
12 22
13 14
13 16
13 17
13 20
13 23
13 24
14 15
14 16
14 18
14 20
14 22
14 23
15 17
15 20
15 24
16 19
16 21
16 22
16 23
17 18
17 19
17 20
17 21
17 23
18 22
18 23
18 24
19 20
19 21
19 24
20 22
20 23
21 22
21 23
21 24
22 24
23 24
Mine too returns 3 on this example. But maybe I have done a subtle error ?Cosmin.ro wrote:My result wich should be the same as domino's since we implemented the same algorithm is 3.