𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem

✍ Scribed by Yupei Xiong; Bruce Golden; Edward Wasil

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
185 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we review recent work on the minimum labeling spanning tree problem and obtain a new worst-case ratio for the MVCA heuristic. We also present a family of graphs in which the worst-case ratio can be attained. This implies that the new ratio cannot be improved any further.

πŸ“œ SIMILAR VOLUMES

The Asymptotic Worst-Case Behavior of th
The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
✍ Kaihong Xu πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 87 KB

The First-Fit-Decreasing FFD algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. The question on the parametric behavior of the FFD heuristic for small items was Ε½ .

Models and heuristics for the k -degree
Models and heuristics for the k -degree constrained minimum spanning tree problem with node-degree costs
✍ Christophe Duhamel; LuΓ­s Gouveia; Pedro Moura; MaurΓ­cio de Souza πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 319 KB πŸ‘ 1 views

## Abstract The __k__ ‐Degree constrained Minimum Spanning Tree Problem (__k__ ‐DMSTP) consists in finding a minimal cost spanning tree satisfying the condition that every node has a degree no greater than a fixed value __k__. Here we consider an extension where besides the edge costs, a concave co

A hierarchy of hop-indexed models for th
A hierarchy of hop-indexed models for the Capacitated Minimum Spanning Tree Problem
✍ Gouveia, Luis; Martins, Pedro πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 143 KB πŸ‘ 2 views

The Capacitated Minimum Spanning Tree Problem (CMSTP) is to find a minimum spanning tree subject to an additional constraint stating that the number of nodes in each subtree pending from a given root node is not greater than a given number Q. Gouveia and Martins (1996) proposed a hop-indexed flow mo