Well, congratulations! Just make sure that the algorithm is correct. To verify it, you can try to count the number of unlabeled graphs with n vertices. Starting with n=0, you should get a list like this:
1,1,2,4,11,34,156,1044,...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000088
1,1,2,4,11,34,156,1044,...
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000088
That''s great. After you publish maybe you should consider writing an article for gamedev.
I appreciate that you are giving more detail than necessary for dramatic effect, but complexities never need more than one term for each variable, and never need scalar co-efficients.
I appreciate that you are giving more detail than necessary for dramatic effect, but complexities never need more than one term for each variable, and never need scalar co-efficients.
quote:Original post by Zefrieg
At least, by the sources I have gone through, mine beats them all!
No need to qualify that statement. In fact, there is no known P algorithm for graph isomporhism testing.
http://mathworld.wolfram.com/GraphIsomorphismComplete.html
Definately copyright the article straight off. Afterward, (and I stress _after_ registering copyright) you might want to find a math professor specializing in graph theory to take a look at it. If everything checks out, I''m sure your algorithm will make it into the math journals.
You might want to patent the algorithm as well (assuming you live in the US or a country that allows it - most don''t let you patent algorithms).
I might be wrong, but I think that your post has a mistake.
The reason for this is the following:
Consider the graphs:
a) 1-2-3-4
b) a-b-c-d
The two are obviously isomorphic. The number of connections is 3 and the total number of vertices is 4 (for one graph).
The complexity of the algorithm is (using your formula):
4*16 + 7*4 + 2*4*log4
but using your second formula:
4*3 + 7*4 + 2*4*log4
If you meant the number of vertices in both graphs (8), and the number of connection in both graphs(6) the formula would still be wrong:
4*64 + ...
4*6 + ...
If you meant the number of vertices in one graph(4) and the number of connections in both graphs(6) the formula
4*16 + ...
4*6 + ...
If you meant the number of vertices in both graphs (8), and the number of connection in one graph (3) the formula is still wrong:
4*8 + ...
4*3 + ...
Obviously, the two are not equal. So I think that there is a mistake in your formulas (if not in your algorithm).
Note that I am not saying here that there does not exist such an algorithm. I am merely pointing out an inconsistency. Also, I might have understood you wrong. In any case, I wish a feedback.
The reason for this is the following:
Consider the graphs:
a) 1-2-3-4
b) a-b-c-d
The two are obviously isomorphic. The number of connections is 3 and the total number of vertices is 4 (for one graph).
The complexity of the algorithm is (using your formula):
4*16 + 7*4 + 2*4*log4
but using your second formula:
4*3 + 7*4 + 2*4*log4
If you meant the number of vertices in both graphs (8), and the number of connection in both graphs(6) the formula would still be wrong:
4*64 + ...
4*6 + ...
If you meant the number of vertices in one graph(4) and the number of connections in both graphs(6) the formula
4*16 + ...
4*6 + ...
If you meant the number of vertices in both graphs (8), and the number of connection in one graph (3) the formula is still wrong:
4*8 + ...
4*3 + ...
Obviously, the two are not equal. So I think that there is a mistake in your formulas (if not in your algorithm).
Note that I am not saying here that there does not exist such an algorithm. I am merely pointing out an inconsistency. Also, I might have understood you wrong. In any case, I wish a feedback.
DeepTrouble
As Zefrieg wrote, the first complexity is for two _complete_ graphs. Which means every vertex is connected to every other vertex. This, in turn, means that if there are n vertices in the graph, then there are (n over 2) edges = n(n-1)/2 which is in the order of n^2.
Congrats, Zefrieg! Assuming the algorithm is correct ofcourse
As Zefrieg wrote, the first complexity is for two _complete_ graphs. Which means every vertex is connected to every other vertex. This, in turn, means that if there are n vertices in the graph, then there are (n over 2) edges = n(n-1)/2 which is in the order of n^2.
Congrats, Zefrieg! Assuming the algorithm is correct ofcourse
quote:Original post by Zefrieg
(4n^2 + 7n + 2n log n) assuming two complete graphs where n is the number of vertices in each graph, or (4m + 7n + 2n log n) where n is the number of vertices and m is the total number of vertex connections.
I cannot fully understand your sentence:
are you treating only complete graphs!?
In this case the cost of verifying ISOMORPHISM is O(1),
i.e. the cost of verifying that the two graphs have the same number of nodes.
bye all
Sorry if I look like a total idiot but I have some trouble understanding this...
Tobbe A, or Zefrieg, please explain me why the heck two complete graphs with the same number of vertices should not be isomorphic???
I mean, when we have 3 vertices, there is one possible graph, a triangle. When there are 4 vertices all the graphs are isomorphic with a square that has its diagonals drawn, etc.
So... isn''t there just a single type of complete graph for n vertices?
Of course, I believe that we are not talking here about directional graphs or something.
In any case, I beg anyone for feedback (I have not a lot of background in graph theory, so please do not be very harsh with me... I do not want to look smart or something).
Tobbe A, or Zefrieg, please explain me why the heck two complete graphs with the same number of vertices should not be isomorphic???
I mean, when we have 3 vertices, there is one possible graph, a triangle. When there are 4 vertices all the graphs are isomorphic with a square that has its diagonals drawn, etc.
So... isn''t there just a single type of complete graph for n vertices?
Of course, I believe that we are not talking here about directional graphs or something.
In any case, I beg anyone for feedback (I have not a lot of background in graph theory, so please do not be very harsh with me... I do not want to look smart or something).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
