Approximating subset k-connectivity problems
From MaRDI portal
Publication:2376789
DOI10.1016/J.JDA.2012.08.001zbMATH Open1281.68237OpenAlexW1975776599MaRDI QIDQ2376789FDOQ2376789
Authors: Zeev Nutov 
Publication date: 24 June 2013
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2012.08.001
Recommendations
- Approximating subset \(k\)-connectivity problems
- Improved approximation algorithms for min-cost connectivity augmentation problems
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Approximating rooted connectivity augmentation problems
- Approximating rooted connectivity augmentation problems
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Cites Work
- An application of submodular flows
- On the ratio of optimal integral and fractional covers
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Improved Approximation Algorithms for Uniform Connectivity Problems
- Approximating node connectivity problems via set covers
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- Approximating k-node Connected Subgraphs via Critical Graphs
- Inapproximability of survivable networks
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
- Tight approximation algorithm for connectivity augmentation problems
- Augmenting undirected node-connectivity by one
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- Approximation Algorithms for Network Design with Metric Costs
- Approximating node-connectivity augmentation problems
- Approximating rooted connectivity augmentation problems
- Title not available (Why is that?)
Cited In (23)
- Spider covering algorithms for network design problems
- Approximating \(k\)-connected \(m\)-dominating sets
- Approximating rooted connectivity augmentation problems
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Improved approximation algorithms for min-cost connectivity augmentation problems
- A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
- Title not available (Why is that?)
- Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems
- Approximating survivable networks with minimum number of Steiner points
- Multi-priority graph sparsification
- Approximating subset \(k\)-connectivity problems
- Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Approximating k-Connected m-Dominating Sets
- Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Survivable network activation problems
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
- Approximating rooted connectivity augmentation problems
This page was built for publication: Approximating subset \(k\)-connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376789)
