scientific article; zbMATH DE number 7053371

MaRDI QIDQ5743494zbMATH OpenFDO

Authors B. Laekhanukit, Guyslain Naves, Adrian Vetta, Joseph Cheriyan

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095235

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximating rooted Steiner networks
• Tighter Bounds for Graph Steiner Tree Approximation
• Approximating Steiner networks with node-weights
• Approximating Steiner Networks with Node Weights
• Approximating Steiner trees in graphs with restricted weights
• scientific article; zbMATH DE number 1445376
• scientific article; zbMATH DE number 1834686
• Approximate Euclidean Steiner trees
• Steiner tree approximation via iterative randomized rounding
• scientific article; zbMATH DE number 2089220

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
• A note on Rooted Survivable Networks
• A Parallel Repetition Theorem
• A threshold of ln n for approximating set cover
• An improved approximation algorithm for minimum-cost subset k-connectivity (extended abstract)
• Applications of approximation algorithms to cooperative games
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximation Algorithms for Directed Steiner Problems
• Design networks with bounded pairwise distance
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• scientific article; zbMATH DE number 5485528 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• Inapproximability of survivable networks
• Parameterized complexity of arc-weighted directed Steiner problems
• Polylogarithmic inapproximability
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• The design of approximation algorithms
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals

Cited in

(5)

• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Approximating subset \(k\)-connectivity problems
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Approximating rooted Steiner networks
• Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs

This page was built for publication:

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