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

A bad example for the iterative rounding method for mincost -connected spanning subgraphs

โœ Scribed by Ashkan Aazami; Joseph Cheriyan; Bundit Laekhanukit

Book ID
119227582
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
596 KB
Volume
10
Category
Article
ISSN
1572-5286

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A linear time 53-approximation for the m
A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem
โœ Liang Zhao; Hiroshi Nagamochi; Toshihide Ibaraki ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 134 KB

A linear time 5 3 -approximation algorithm is presented for the NP-hard problem of finding a minimum strongly-connected spanning subgraph. It is based on cycle contraction that was first introduced by Khuller, Raghavachari and Young [SIAM J. Comput. 24 (1995) 859-872]. We improve their result by con

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