𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The full-degree spanning tree problem

✍ Scribed by Randeep Bhatia; Samir Khuller; Robert Pless; Yoram J. Sussmann

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
136 KB
Volume
36
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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 almost-optimal optimal optimal approximation algorithms for it assuming that coR coR coR β‰  β‰  β‰  NP NP NP. For the case of general graphs, our approximation factor is Θ( √ n n n). Using HΓ₯stad's result on the hardness of an approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of O O O(n n n 1/2-) then coR coR coR = NP NP NP. Additionally, we present two algorithms for optimally solving small instances of the general problem and experimental results comparing our algorithm to the optimal solution and the previous heuristic used for this problem.

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