Online Steiner Tree with Deletions

DOI10.1137/1.9781611973402.34zbMath1421.68249arXiv1312.7296OpenAlexW4206501214MaRDI QIDQ5383994

Anupam Gupta, Amit Kumar

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.7296

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (11)

Online maximum matching with recourse ⋮ The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online ⋮ Online knapsack with removal and recourse ⋮ Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem ⋮ Unnamed Item ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Online Maximum Matching with Recourse ⋮ Unnamed Item ⋮ The Power of Recourse for Online MST and TSP ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems

This page was built for publication: Online Steiner Tree with Deletions