An almost O( k)-approximation for k-connected subgraphs

zbMATH Open1422.68309MaRDI QIDQ4633904FDOQ4633904

Authors: Zeev Nutov 

Publication date: 6 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=1496869

Recommendations

• Approximating node connectivity problems via set covers
• A note on Rooted Survivable Networks
• scientific article; zbMATH DE number 1670542
• Approximating subset \(k\)-connectivity problems
• Approximating minimum-cost connectivity problems via uncrossable bifamilies

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)

Cited In (11)

• On minimum power connectivity problems
• A note on Rooted Survivable Networks
• Inapproximability of survivable networks
• Approximating node connectivity problems via set covers
• A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Title not available (Why is that?)
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Approximating fault-tolerant group-Steiner problems
• Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
• Approximating minimum-power edge-covers and 2,3-connectivity

This page was built for publication: An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633904)