Online Node-Weighted Steiner Tree and Related Problems

DOI10.1109/FOCS.2011.65zbMath1292.68128OpenAlexW2000793193MaRDI QIDQ5494965

Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.65

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (18)

Tight bounds for online weighted tree augmentation ⋮ Unnamed Item ⋮ Non-greedy online Steiner trees on outerplanar graphs ⋮ Online Buy-at-Bulk Network Design ⋮ Timing matters: online dynamics in broadcast games ⋮ Unnamed Item ⋮ Locating service and charging stations ⋮ Online Spanners in Metric Spaces ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Non-greedy Online Steiner Trees on Outerplanar Graphs ⋮ The relation of connected set cover and group Steiner tree ⋮ On the hardness of full Steiner tree problems ⋮ The Bursty Steiner Tree Problem ⋮ Covering problems in edge- and node-weighted graphs ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Tight Bounds for Online Weighted Tree Augmentation ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems

This page was built for publication: Online Node-Weighted Steiner Tree and Related Problems