✦ LIBER ✦

A Constant Factor Approximation for Minimum -Edge-Connected -Subgraph with Metric Costs

✍ Scribed by Safari, MohammadAli; Salavatipour, Mohammad R.

Book ID: 118197043
Publisher: Society for Industrial and Applied Mathematics
Year: 2011
Tongue: English
Weight: 445 KB
Volume: 25
Category: Article
ISSN: 0895-4801
DOI: 10.1137/080729918

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

An approximation algorithm for finding a

An approximation algorithm for finding ad-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

✍ A. E. Baburin; E. Kh. Gimadi 📂 Article 📅 2008 🏛 Pleiades Publishing 🌐 English ⚖ 713 KB