Approximating \(k\)-generalized connectivity via collapsing HSTs
type: Item
instance of: scholarly article
title: Approximating \(k\)-generalized connectivity via collapsing HSTs
zbMATH Open document ID: 1319.05128
author: Danny Segev
published in: Journal of Combinatorial Optimization
publication date: 2015-08-24T00:00:00Z
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6475137
zbMATH Keywords: approximation algorithms
zbMATH Keywords: generalized connectivity
zbMATH Keywords: probabilistic embedding into HSTs
zbMATH Keywords: group Steiner tree
zbMATH Keywords: dense \(k\)-subgraph
MaRDI profile type: Publication
full work available at URL: s10878-009-9256-3
OpenAlex ID: W2050873015
cites work: When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
cites work: A general approach to online network optimization problems
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: Proof verification and the hardness of approximation problems
cites work: Greedily Finding a Dense Subgraph
cites work: On-line generalized Steiner problem
cites work: Q4542533
cites work: Approximating min-sum k -clustering in metric spaces
cites work: Q4527000
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Q4542528
cites work: Q3579405
cites work: A greedy approximation algorithm for the group Steiner problem
cites work: Q2934722
cites work: Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
cites work: On network design problems: fixed cost flows and the covering steiner problem
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: The dense \(k\)-subgraph problem
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: Improved approximation algorithms for directed Steiner forest
cites work: Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
cites work: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: Dial a Ride from k-Forest
cites work: Q2934710
cites work: Automata, Languages and Programming
cites work: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
cites work: Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
cites work: Polylogarithmic inapproximability
cites work: An improved rounding method and semidefinite programming relaxation for graph partition
cites work: Maximum Gradient Embeddings and Monotone Clustering
cites work: Optimization, approximation, and complexity classes
cites work: Matching Based Augmentations for Approximating Connectivity Problems
cites work: Q4694752
cites work: Tighter Bounds for Graph Steiner Tree Approximation
cites work: Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
cites work: Q2934723
cites work: A Tight Analysis of the Greedy Algorithm for Set Cover
cites work: New approaches to covering and packing problems
cites work: Q4828915
DOI: 10.1007/S10878-009-9256-3
Recommended article: Approximating subset \(k\)-connectivity problems
Recommended article: Approximating Subset k-Connectivity Problems
Recommended article: Approximating k-Connected m-Dominating Sets
Recommended article: Approximating \(k\)-connected \(m\)-dominating sets
Recommended article: k-Edge-Connectivity: Approximation and LP Relaxation
Recommended article: Approximating k-node Connected Subgraphs via Critical Graphs
Recommended article: Q4633904
Recommended article: Note on the hardness of generalized connectivity
Recommended article: The \(k\)-hop connected dominating set problem: approximation and hardness
description: scientific article; zbMATH DE number 6475137