0
$\begingroup$

Let $G=(V,E)$ be graph, I know that $\Sigma_{v\in V}d(v)=O(|V|+|E|)$.

In my algorithm I go over each $v$ and for each $v$ I look at all of his neighbors and their neighbors and I do constant time work on each of them.

There are $d(v)$ neighbors for $v$, and if $v'$ is a neighbor of $v$ then he have $d(v')$ neighbors. This gives the sum $\Sigma_{v\in V}(d(v)(\Sigma_{v'}d(v'))$ where $v'$ in the index of the second sum goes over all the neighbors of $v$.

What is the time complexity of my algorithm ? what is a tight bound for the above sum ?

What is the time complexity of my algorithm when the graph is directed ? now we have $d_{out}$ wherever we had $d$ in the above sum

  • 0
    @mjqxxxx - what question ? http://cstheory.stackexchange.com/users/7956/belgi2012-10-21

1 Answers 1

1

I think that you need some more information on the graph. For a general graph with $n$ vertices, the above sum is maximized for a complete graph. As for a complete graph: $\Sigma_{v\in V}(d(v)(\Sigma_{v'}d(v')) = n(n-1)(n-1) = O(n^3) = O(|V|^3) = O(|E|^{1.5})$

As I said those bounds are achieved for the complete graph, so they are tight.