𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Stochastic spanning tree problem

✍ Scribed by Hiroaki Ishii; Shōgo Shiode; Toshio Nishida; Yoshikazu Namasuya

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
485 KB
Volume
3
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On stochastic spanning tree problem
On stochastic spanning tree problem
✍ S. Geetha; K. P. K. Nair 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 443 KB

This paper considers a generalized version of the stochastic spanning tree problem in which edge costs are random variables and the objective is to find a spectrum of optimal spanning trees satisfying a certain chance constraint whose right-hand side also is treated as a decision variable. A special

Stochastic bottleneck spanning tree prob
Stochastic bottleneck spanning tree problem
✍ Hiroaki Ishii; Toshio Nishida 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 296 KB

This paper considers a stochastic version of bottleneck spanning tree problem in which edge costs are random variables. The problem is to find an optimal spanning tree under the chance constraint with respect to bottleneck (maximum cost) edge of spanning tree. The problem is first transformed into a

The full-degree spanning tree problem
The full-degree spanning tree problem
✍ Randeep Bhatia; Samir Khuller; Robert Pless; Yoram J. Sussmann 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB

The full-degree spanning tree problem is defined as follows: Given a connected graph G G G = (V V V, E E E), find a spanning tree T T T to maximize the number of vertices whose degree in T T T is the same as in G G G (these are called vertices of "full" degree). This problem is NP-hard. We present a