Approximating k-generalized connectivity via collapsing HSTs

DOI10.1007/S10878-009-9256-3zbMATH Open1319.05128OpenAlexW2050873015MaRDI QIDQ491201FDOQ491201

Authors: Danny Segev 

Publication date: 24 August 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9256-3

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

zbMATH Keywords

approximation algorithmsgroup Steiner treegeneralized connectivitydense \(k\)-subgraphprobabilistic embedding into HSTs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Programming involving graphs or networks (90C35) Trees (05C05) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60) Connectivity (05C40)

Cites Work

• Optimization, approximation, and complexity classes
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• A greedy approximation algorithm for the group Steiner problem
• Approximation algorithms for maximization problems arising in graph partitioning
• On network design problems: fixed cost flows and the covering steiner problem
• Proof verification and the hardness of approximation problems
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A General Approximation Technique for Constrained Forest Problems
• Approximation Algorithms for Directed Steiner Problems
• Greedily Finding a Dense Subgraph
• Tighter Bounds for Graph Steiner Tree Approximation
• A tight bound on approximating arbitrary metrics by tree metrics
• The dense \(k\)-subgraph problem
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• An improved rounding method and semidefinite programming relaxation for graph partition
• A general approach to online network optimization problems
• Approximation algorithms for node-weighted buy-at-bulk network design
• Matching Based Augmentations for Approximating Connectivity Problems
• Title not available (Why is that?)
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Improved approximation algorithms for directed Steiner forest
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Dial a Ride from k-Forest
• An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem
• Title not available (Why is that?)
• Approximating min-sum k -clustering in metric spaces
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• On-line generalized Steiner problem
• New approaches to covering and packing problems
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Maximum Gradient Embeddings and Monotone Clustering
• Title not available (Why is that?)
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
• Automata, Languages and Programming

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)