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

An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem

โœ Scribed by Fakcharoenphol, Jittat; Laekhanukit, Bundit

Book ID
118177300
Publisher
Society for Industrial and Applied Mathematics
Year
2012
Tongue
English
Weight
254 KB
Volume
41
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A 2-Approximation Algorithm for Finding
A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
โœ Vincenzo Auletta; Yefim Dinitz; Zeev Nutov; Domenico Parente ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 71 KB

The problem of finding a minimum weight k-vertex connected spanning sub-ลฝ . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs ลฝ and of k-out-connected graphs i.e., graphs which contain a vertex