Online node-weighted Steiner tree and related problems

DOI10.1109/FOCS.2011.65MaRDI QIDQ5494965zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Near-optimal online algorithms for prize-collecting Steiner problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• An optimal algorithm for online prize-collecting node-weighted Steiner forest
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• scientific article; zbMATH DE number 1559550

Cited in

(25)

• Pick, pack, \& survive: charging robots in a modern warehouse based on online connected dominating sets
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• On-line generalized Steiner problem
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Tight bounds for online weighted tree augmentation
• Spider covering algorithms for network design problems
• Tight bounds for online weighted tree augmentation
• Online Buy-at-Bulk Network Design
• Online weighted degree-bounded Steiner networks via novel online mixed packing/covering
• Online degree-bounded Steiner network design
• Non-greedy online Steiner trees on outerplanar graphs
• Near-optimal online algorithms for prize-collecting Steiner problems
• Greedy algorithms for online survivable network design
• The relation of connected set cover and group Steiner tree
• Locating service and charging stations
• Online Directed Spanners and Steiner Forests.
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• scientific article; zbMATH DE number 6381651 (Why is no real title available?)
• Non-greedy online Steiner trees on outerplanar graphs
• Online Spanners in Metric Spaces
• An optimal algorithm for online prize-collecting node-weighted Steiner forest
• On the hardness of full Steiner tree problems
• The bursty Steiner tree problem
• Timing matters: online dynamics in broadcast games
• Approximation algorithms for priority Steiner tree problems

This page was built for publication: Online node-weighted Steiner tree and related problems

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