Greedy algorithms for online survivable network design

DOI10.4230/LIPICS.ICALP.2018.152MaRDI QIDQ5002841zbMATH OpenFDO

Authors Sina Dehghani, Soheil Ehsani, Vahid Liaghat, S. Seddighin, Mohammad T. Hajiaghayi

Publication date 28 July 2021

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2018.152

zbMATH Keywords

greedy algorithmonline algorithmsurvivable network design

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Online and Stochastic Survivable Network Design
• Online and stochastic survivable network design
• Online degree-bounded Steiner network design
• A general approach to online network optimization problems
• scientific article; zbMATH DE number 6469194

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A General Approximation Technique for Constrained Forest Problems
• A Graph Reduction Step Preserving Element-Connectivity and Applications
• A primal-dual approximation algorithm for generalized Steiner network problems
• An O( n)-competitive algorithm for online constrained forest problems
• Bounds on the maximum number of edge-disjoint Steiner trees of a graph
• Dynamic Steiner Tree Problem
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-disjoint trees containing some given vertices in a graph
• Hardness and approximation results for packing Steiner trees
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 5764797 (Why is no real title available?)
• scientific article; zbMATH DE number 1263259 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• scientific article; zbMATH DE number 1559550 (Why is no real title available?)
• Near-optimal online algorithms for prize-collecting Steiner problems
• On-line generalized Steiner problem
• Online and Stochastic Survivable Network Design
• Online node-weighted Steiner tree and related problems
• Randomized metarounding (extended abstract)
• The online set cover problem

Cited in

(8)

• On approximating degree-bounded network design problems
• Online degree-bounded Steiner network design
• Online and Stochastic Survivable Network Design
• Bounded Degree Group Steiner Tree Problems
• Tight bounds for online weighted tree augmentation
• Online and stochastic survivable network design
• Prophet secretary for combinatorial auctions and matroids
• Tight bounds for online weighted tree augmentation

This page was built for publication: Greedy algorithms for online survivable network design

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