Set connectivity problems in undirected graphs and the directed Steiner network problem

DOI10.1145/1921659.1921664MaRDI QIDQ3189000zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1921659.1921664

zbMATH Keywords

approximation algorithmsdirected Steiner networkgeneralized connectivity

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• scientific article; zbMATH DE number 1303557
• Approximation Algorithms for Directed Steiner Problems
• Approximating node connectivity problems via set covers

Cited in

(33)

• Directed Steiner problems with connectivity constraints
• Approximation algorithm for the partial set multi-cover problem
• Bayesian generalized network design
• Approximation algorithms for constructing some required structures in digraphs
• The subdivision-constrained routing requests problem
• Balls and funnels: energy efficient group-to-group anycasts
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Approximation algorithms for orienting mixed graphs
• Online Buy-at-Bulk Network Design
• Spider covering algorithms for network design problems
• Approximating rooted Steiner networks
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Parameterized approximation algorithms for bidirected Steiner network problems
• Bayesian generalized network design
• Complexity of the Steiner Network Problem with Respect to the Number of Terminals
• How to Secure Matchings against Edge Failures
• On survivable set connectivity
• The Set Connector Problem in Graphs
• An ETH-tight algorithm for bidirected Steiner connectivity
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• On approximating partial scenario set cover
• The parameterized complexity of the survivable network design problem
• On the bidirected cut relaxation for Steiner forest
• Finding smallest witnesses for conjunctive queries
• The complexity landscape of fixed-parameter directed Steiner network problems
• The strongish planted clique hypothesis and its consequences
• Approximation algorithms for directed weighted spanners
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• From directed Steiner tree to directed polymatroid Steiner tree in planar graphs
• An approximation algorithm for generalized connectivity problem on planar graphs
• Directed buy-at-bulk spanners
• Approximation algorithms for optimal hopsets
• On minimum generalized Manhattan connections

This page was built for publication: Set connectivity problems in undirected graphs and the directed Steiner network problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189000)