I'm trying to find an answer to a problem in my Distributed Algorithms course, and to do so I want to get something clarified.
If you are interested, the question to which I'm trying to find an answer is this:
In terms of n (# nodes), the number of messages (= diam * |E|) used in the FloodMax algorithm is easily seen to be O(n^3). Produce a class of digraphs in which the product (diam * |E|) really is Omega(n^3).
The digraph I came up with is a graph with just one node, which has a directed edge to itself. That way |E| would be 1 which is n^2, and if the diam is 1, it satisfies the second condition where diam = 1 = n as well. So it gives me a class of digraphs with message complexity being Omega(n^3).
So am I correct in my thinking, that in such a graph the diameter is 1?
Two things:
It seems to be 0 according to this, which says:
In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
Your solution to the given problem should describe how to build a graph (or rather say what type of known graph has that property, since it says "produce a class") with n
nodes, not a graph with however many nodes you manually figured out a solution for. I can do the same for 2 nodes:
1 -- 2
|E| = 1 = (1/4)*2^2 = (1/4)*n^2 = O(n^2)
diam = 1 = 2 - 1 = n - 1 = O(n)
tada!
Or here's how we can make your solution work even if the diameter is 0: 0 = 1 - 1 = n - 1 = O(n) => your solution still works!
So even if you considered paths with loops as well, I would still deem your solution incorrect.