Approximating fault-tolerant group-Steiner problems

DOI10.4230/LIPICS.FSTTCS.2009.2324zbMATH Open1248.68383OpenAlexW2279143674MaRDI QIDQ2920133FDOQ2920133

Authors: Rohit Khandekar, Guy Kortsarz, Zeev Nutov 

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_e9bf.html

Recommendations

• Approximating fault-tolerant group-Steiner problems
• scientific article; zbMATH DE number 2119643
• scientific article; zbMATH DE number 139784
• An improved approximation scheme for the Group Steiner Problem
• Approximation algorithm for the group Steiner network problem
• A greedy approximation algorithm for the group Steiner problem
• scientific article; zbMATH DE number 1303564
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• On Group Graphs and Their Fault Tolerance
• An FPTAS for the fractional group Steiner tree problem

zbMATH Keywords

approximationfault-toleranceconnectivitygroup Steiner problemedge-disjointnessvertex-disjointness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cited In (4)

• The relation of connected set cover and group Steiner tree
• Approximation algorithms for minimum weight partial connected set cover problem
• Approximating fault-tolerant group-Steiner problems
• Survivable network design for group connectivity in low-treewidth graphs

This page was built for publication: Approximating fault-tolerant group-Steiner problems

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