5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user5810
    Commented Mar 26, 2014 at 14:09
  • $\begingroup$ @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. $\endgroup$
    – Andre Holzner
    Commented Mar 26, 2014 at 16:15
  • $\begingroup$ @RickyDemer: Indeed. Fixed. $\endgroup$
    – Adi Shavit
    Commented Mar 26, 2014 at 18:11

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .