Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we have $w(v,y) \leq w(v,u)+w(u,y)$.
However, it is expensive to calculate $w(\cdot)$.

My question is, is there an algorithm that can calculate the minimum spanning tree, without calculating all $n(n-1)/2$ edge weights?

share|improve this question
    
Is the graph directed? $\:$ If no, then there are only $(n\cdot (n\hspace{-0.04 in}-\hspace{-0.05 in}1))/2$ edge weights. $\;\;\;\;$ –  Ricky Demer Mar 26 at 14:09
    
@Ricky Demer $w$ seems to be a metric and a metric is symmetric, so there should indeed only be $n \cdot (n-1) / 2$ edge weights. –  Andre Holzner Mar 26 at 16:15
    
@RickyDemer: Indeed. Fixed. –  Adi Shavit Mar 26 at 18:11

1 Answer 1

up vote 7 down vote accepted

In general the triangle inequality will not help. To see this, recall that the minimum spanning tree depends only on the relative order of the weights. Take an arbitrary MST problem and scale all the weights to lie in $[2,3]$. Now the triangle inequality is satisfied but the MST is the same.

To put it another way, if in your problem the edge weights all happen to lie in $[2,3]$, you must find the weight of every edge since the one you didn't find the weight of can still be the smallest no matter what the weights of all the other edges are.

On the other hand, I can imagine a heuristic that accumulates lower bounds and often argues itself out of computing weights of some edges in practical problems. It just can't guarantee to perform better than standard algorithms in the worst case.

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.