## Search found 40 matches

- Thu Jan 13, 2005 11:00 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10805 - Cockroach Escape Networks
- Replies:
**38** - Views:
**13163**

### Re: 10805 Cockroach Escape Networks

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 ...

- Thu Jan 13, 2005 9:24 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10805 - Cockroach Escape Networks
- Replies:
**38** - Views:
**13163**

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 :) First , my remark that the code would be ver...

- Thu Jan 13, 2005 8:32 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10805 - Cockroach Escape Networks
- Replies:
**38** - Views:
**13163**

[ Case 2: The minimum diameter spanning tree T has an even diameter d(meaning the longest path has an even number of vertices.) 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...

- Thu Jan 13, 2005 7:10 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10805 - Cockroach Escape Networks
- Replies:
**38** - Views:
**13163**

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 -...

- Thu Jan 06, 2005 7:48 pm
- Forum: Volume 1 (100-199)
- Topic: 108 - Maximum Sum
- Replies:
**233** - Views:
**22542**

Do you think you can solve this in O(n^2), because I thought only O(n^3) exists. :roll: have you got a profe on this O(n^2) theorem? I really, really don't think there's an easy O(N^2) algo for this algo (and by easy I mean necessitating less than a lifetime of research) . It's been an open problem...

- Thu Jan 06, 2005 4:10 pm
- Forum: Algorithms
- Topic: Exact matching subimages
- Replies:
**5** - Views:
**1470**

I think I got an O(N^3 lg(N) ) expected time algorithm . Here it is : First note that we can check whether there is a common submatrix of size W*H in O(N^2) time, (W and H are given) ,by getting a hash value for each W*H submatrix in the first matrix , putting these hash values in a hash table and t...

- Wed Jan 05, 2005 8:15 pm
- Forum: Algorithms
- Topic: Exact matching subimages
- Replies:
**5** - Views:
**1470**

- Wed Jan 05, 2005 4:15 pm
- Forum: Algorithms
- Topic: Exact matching subimages
- Replies:
**5** - Views:
**1470**

OK the best I got is O(N^4). Here is how I do it: I try all possible values for (x1-x2) and (y1-y2). To check what is the maximum common submatrix with given values of (x1-x2) and (y1-y2) , I shift the matrix M2 by (x1-x2) horizontally and (y1-y2) vertically , and I obtain a new matrix M2' . (shifti...

- Sun Dec 05, 2004 1:18 am
- Forum: Algorithms
- Topic: Deikstra with heap
- Replies:
**5** - Views:
**1759**

- Sun Dec 05, 2004 1:12 am
- Forum: Algorithms
- Topic: k-th shortest path
- Replies:
**2** - Views:
**1239**

You might wish to see this web page:

http://terra.act.uji.es/REA/

http://terra.act.uji.es/REA/