𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating minimum-cost graph problems with spanning tree edges

✍ Scribed by Michel X. Goemans; David P. Williamson

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
435 KB
Volume
16
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Covering the Edges of a Graph by a Presc
Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap
✍ Noga Alon; Yair Caro; Raphael Yuster πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 360 KB

Let H=(V H , E H ) be a graph, and let k be a positive integer. A graph G=(V G , E G ) is H-coverable with overlap k if there is a covering of the edges of G by copies of H such that no edge of G is covered more than k times. Denote by overlap(H, G) the minimum k for which G is H-coverable with over

A Better Approximation Ratio for the Min
A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
✍ Cristina G Fernandes πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 213 KB

Consider the minimum size k-edge-connected spanning subgraph problem: given a positive integer k and a k-edge-connected graph G, find a k-edge-connected spanning subgraph of G with the minimum number of edges. This problem is known to be NP-complete. Khuller and Raghavachari presented the first algo