[-] Q4
by sepetnit - Wednesday, 15 July 2009 17:29:27
Should we refer to the graph representation in bits in order to prove that our algorithms are polynomial in |V| and |E|?
If so, what is the size in bits of a graph G = (V, E)? 
thread
Re: Q4
by golansha - Wednesday, 15 July 2009 20:47:58
the graph representation takes log|V|+ |E| log|V|.
However, if you prove that the problem is polynomial in |E| (which is "cleaner") and say that the input size is at least |E|, it is also OK. 
thread