Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
These are both going to be $O(n^{3})$. Assuming this is related to your cstheory question? –  mjqxxxx Oct 21 '12 at 20:47
    
@mjqxxxx - what question ? cstheory.stackexchange.com/users/7956/belgi –  Belgi Oct 21 '12 at 20:49

1 Answer 1

up vote 1 down vote accepted
+50

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.