Minimum Spanning Tree of a Weighted Graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:16:44Z http://mathoverflow.net/feeds/question/28761 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28761/minimum-spanning-tree-of-a-weighted-graph Minimum Spanning Tree of a Weighted Graph MAKCL 2010-06-19T16:55:18Z 2010-06-19T22:00:22Z <p>I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \leq r(u,v)+r(v,w)$. We furthermore have the following condition: $\sum_{u\in V}R(u) \leq n$ where $R(u)$ is the average of the weights of the edges incident on $u$.</p> <p>My question is, does there exist a minimum spanning tree, that has weight at most $Cn$ where $C$ is some universal constant? In place of a minimum weight spanning tree, a walk (sequence of connected vertices) such that the sum of weights of the walk is $Cn$ for some universal constant.</p> http://mathoverflow.net/questions/28761/minimum-spanning-tree-of-a-weighted-graph/28765#28765 Answer by Tony Huynh for Minimum Spanning Tree of a Weighted Graph Tony Huynh 2010-06-19T17:08:26Z 2010-06-19T17:45:03Z <p>I think the answer is <strong>no</strong> for both questions. Let $T$ be the unique tree on $2n$ vertices with two adjacent vertices $u$ and $v$ of degree $n$. Let $e=uv$. Let the weight of $e$ be $n^2$ and all other edges to have weight 0. Then the sum of all the average weights is </p> <p>$n^2/n + n^2/n = 2n = |V(T)|$. </p> <p>However, $T$ has total weight $n^2$, which is not $O(2n)$. </p> <p><strong>Comment.</strong> I edited my first answer as I misread the condition on the average degrees. </p> http://mathoverflow.net/questions/28761/minimum-spanning-tree-of-a-weighted-graph/28781#28781 Answer by SandeepJ for Minimum Spanning Tree of a Weighted Graph SandeepJ 2010-06-19T22:00:22Z 2010-06-19T22:00:22Z <p>You need some variant of the degree-constrained GMST (Generalized Minimum Spanning Tree) with edges satisfying the triangle inequality. These are some pointers to literature.</p> <ol> <li><p>Bruce Boldon, Narsingh Deo and Nishit Kumar.<a href="http://dx.doi.org/10.1016/0167-8191%2895%2900010-0" rel="nofollow">Minimum-weight degree-constrained spanning tree problem</a></p> <p>The minimum spanning tree problem with an added constraint that no node in the spanning tree has the degree more than a specified integer, d, is known as the minimum-weight degree-constrained spanning tree (d-MST) problem. Such a constraint arises, for example, in VLSI routing trees, in backplane wiring, or in minimizing single-point failures for communication networks. The d-MST problem is NP-complete. Here, we develop four heuristics for approximate solutions to the problem and implement them on a massivelyparallel SIMD machine, MasPar MP-1. An extensive empirical study shows that for random graphs on up to 5000 nodes (about 12.5 million edges), the heuristics produce solutions close to the optimal in less than 10 seconds. The heuristics were also tested on a number of TSP benchmark problems to compute spanning trees with a degree bound d = 3.</p></li> <li><p>MR1469650 (98h:68181) Fekete, Sándor P. ; Khuller, Samir ; Klemmstein, Monika ; Raghavachari, Balaji ; Young, Neal . <a href="http://dx.doi.org/10.1006/jagm.1997.0862" rel="nofollow">A network-flow technique for finding low-weight bounded-degree spanning trees</a>. J. Algorithms 24 (1997), no. 2, 310--324. </p></li> <li>MR1469648 (98d:68165) Guttmann-Beck, Nili ; Hassin, Refael . <a href="http://dx.doi.org/10.1006/jagm.1996.0848" rel="nofollow">Approximation algorithms for min-max tree partition</a>. J. Algorithms 24 (1997), no. 2, 266--286.</li> <li>MR2006103 (2004h:68154) Hassin, Refael ; Levin, Asaf . <a href="http://dx.doi.org/10.1016/S0196-6774%2803%2900051-8" rel="nofollow">Minimum spanning tree with hop restrictions</a>. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001). J. Algorithms 48 (2003), no. 1, 220--238.</li> <li>MR2480226 (2010f:68072) Srivastav, Anand ; Werth, Sören . <a href="http://www.springerlink.com/content/q71374711716628p/" rel="nofollow">Probabilistic analysis of the degree bounded minimum spanning tree problem</a>. FSTTCS 2007: Foundations of software technology and theoretical computer science, 497--507, Lecture Notes in Comput. Sci., 4855, Springer, Berlin, 2007.</li> </ol>