Approximating k-generalized connectivity via collapsing HSTs
From MaRDI portal
(Redirected from Publication:491201)
Approximating \(k\)-generalized connectivity via collapsing HSTs
Approximating \(k\)-generalized connectivity via collapsing HSTs
Recommendations
- Approximating subset \(k\)-connectivity problems
- Approximating subset \(k\)-connectivity problems
- Approximating k-Connected m-Dominating Sets
- Approximating \(k\)-connected \(m\)-dominating sets
- \(k\)-edge-connectivity: approximation and LP relaxation
- Approximating k-node Connected Subgraphs via Critical Graphs
- An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
- Note on the hardness of generalized connectivity
- The k-hop connected dominating set problem: approximation and hardness
Cites work
- scientific article; zbMATH DE number 1559550 (Why is no real title available?)
- scientific article; zbMATH DE number 1775395 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- scientific article; zbMATH DE number 219265 (Why is no real title available?)
- scientific article; zbMATH DE number 2119644 (Why is no real title available?)
- A General Approximation Technique for Constrained Forest Problems
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- A Tight Analysis of the Greedy Algorithm for Set Cover
- A general approach to online network optimization problems
- A greedy approximation algorithm for the group Steiner problem
- A tight bound on approximating arbitrary metrics by tree metrics
- An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem
- An improved rounding method and semidefinite programming relaxation for graph partition
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
- Approximating min-sum k -clustering in metric spaces
- Approximation Algorithms for Directed Steiner Problems
- Approximation algorithms for maximization problems arising in graph partitioning
- Approximation algorithms for node-weighted buy-at-bulk network design
- Approximation algorithms for prize collecting forest problems with submodular penalty functions
- Automata, Languages and Programming
- Dial a Ride from k-Forest
- Greedily Finding a Dense Subgraph
- Improved approximation algorithms for directed Steiner forest
- Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
- Matching Based Augmentations for Approximating Connectivity Problems
- Maximum Gradient Embeddings and Monotone Clustering
- New approaches to covering and packing problems
- On network design problems: fixed cost flows and the covering steiner problem
- On-line generalized Steiner problem
- Optimization, approximation, and complexity classes
- Polylogarithmic inapproximability
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Proof verification and the hardness of approximation problems
- Set connectivity problems in undirected graphs and the directed Steiner network problem
- Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
- The dense \(k\)-subgraph problem
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Tighter Bounds for Graph Steiner Tree Approximation
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Cited in
(5)- Set connectivity problems in undirected graphs and the directed Steiner network problem
- Augmenting weighted graphs to establish directed point-to-point connectivity
- Set connectivity problems in undirected graphs and the directed Steiner network problem
- On kernelization and approximation for the vector connectivity problem
- On kernelization and approximation for the vector connectivity problem
This page was built for publication: Approximating \(k\)-generalized connectivity via collapsing HSTs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491201)
