Approximating \(k\)-generalized connectivity via collapsing HSTs

DOI10.1007/S10878-009-9256-3zbMath1319.05128OpenAlexW2050873015MaRDI QIDQ491201

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (1)

Augmenting weighted graphs to establish directed point-to-point connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for directed Steiner forest
• Optimization, approximation, and complexity classes
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• 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
• On-line generalized Steiner problem
• A greedy approximation algorithm for the group Steiner problem
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• On network design problems: fixed cost flows and the covering steiner problem
• A general approach to online network optimization problems
• Proof verification and the hardness of approximation problems
• Matching Based Augmentations for Approximating Connectivity Problems
• Dial a Ride from k-Forest
• Polylogarithmic inapproximability
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Maximum Gradient Embeddings and Monotone Clustering
• A Tight Analysis of the Greedy Algorithm for Set Cover
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximation Algorithms for Directed Steiner Problems
• Greedily Finding a Dense Subgraph
• Approximating min-sum k -clustering in metric spaces
• Tighter Bounds for Graph Steiner Tree Approximation
• 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
• A tight bound on approximating arbitrary metrics by tree metrics
• The dense \(k\)-subgraph problem

This page was built for publication: Approximating \(k\)-generalized connectivity via collapsing HSTs