๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Stochastic bottleneck spanning tree problem

โœ Scribed by Hiroaki Ishii; Toshio Nishida

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
296 KB
Volume
13
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 deterministic equivalent problem. Then its subproblem is introduced and a close relation between these problems is clarified. Finally, based on the relation, an algorithm which finds an optimal spanning tree of the original problem in a polynomial order of its problem size is proposed.

๐Ÿ“œ 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

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

A Faster Algorithm for the Inverse Spann
A Faster Algorithm for the Inverse Spanning Tree Problem
โœ Ravindra K. Ahuja; James B. Orlin ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 149 KB

In this paper, we consider the inverse spanning tree problem. Given an undi-0 ลฝ 0 0 . rected graph G s N , A with n nodes, m arcs, an arc cost vector c, and a spanning tree T 0 , the inverse spanning tree problem is to perturb the arc cost vector c to a vector d so that T 0 is a minimum spanning tre