𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Value of a Random Minimum Weight Steiner Tree

✍ Scribed by Béla Bollobás*; David Gamarnik; Oliver Riordan; Benny Sudakov†

Publisher
Springer-Verlag
Year
2004
Tongue
English
Weight
263 KB
Volume
24
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On finding a minimum spanning tree in a
On finding a minimum spanning tree in a network with random weights
✍ Colin McDiarmid; Theodore Johnson; Harold S. Stone 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 2 views

We investigate Prim's standard ''tree-growing'' method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e Ž . have independent identically distributed random weights w e . We find that when the kth ' Ž . edge e is added to the current tree

Approximating the Minimum-Degree Steiner
Approximating the Minimum-Degree Steiner Tree to within One of Optimal
✍ M. Furer; B. Raghavachari 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 691 KB

The problem of constructing a spanning tree for a graph \(G=(V, E)\) with \(n\) vertices whose maximal degree is the smallest among all spanning trees of \(G\) is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of dist

On the Steiner median of a tree
On the Steiner median of a tree
✍ Lowell W. Beineke; Ortrud R. Oellermann; Raymond E. Pippert 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 639 KB
A linear programming approach to increas
A linear programming approach to increasing the weight of all minimum spanning trees
✍ Mourad Baïou; Francisco Barahona 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. Frederickson and Solis‐Oba gave an