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

MaRDI QIDQ3579405zbMATH OpenFDO

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

Publication date 6 August 2010

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Connectivity (05C40)

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
• scientific article; zbMATH DE number 7053371

Cited in

(10)

• How to Secure Matchings Against Edge Failures
• Approximating rooted Steiner networks
• Improved approximation algorithms for directed Steiner forest
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• Pruning 2-connected graphs
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• The Set Connector Problem in Graphs
• Directed Steiner problems with connectivity constraints
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• On survivable set connectivity

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 Q3579405)