Online Node-weighted Steiner Forest and Extensions via Disk Paintings
From MaRDI portal
Publication:5737814
DOI10.1137/14098692XzbMath1370.68335OpenAlexW2620451143MaRDI QIDQ5737814
Debmalya Panigrahi, Vahid Liaghat, Mohammad Taghi Hajiaghayi
Publication date: 30 May 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/14098692x
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items (8)
Tight bounds for online weighted tree augmentation ⋮ Online Buy-at-Bulk Network Design ⋮ Timing matters: online dynamics in broadcast games ⋮ Online Spanners in Metric Spaces ⋮ Covering problems in edge- and node-weighted graphs ⋮ Online constrained forest and prize-collecting network design ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems
Cites Work
- Unnamed Item
- Unnamed Item
- Lower bound of the Hadwiger number of graphs by their average degree
- The point-to-point delivery and connection problems: Complexity and algorithms
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- On-line generalized Steiner problem
- Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Efficient recovery from power outage (extended abstract)
- Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
- A general approach to online network optimization problems
- An O(logn)-Competitive Algorithm for Online Constrained Forest Problems
- The Online Set Cover Problem
- The Design of Competitive Online Algorithms via a Primal—Dual Approach
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- Heuristics for the fixed cost median problem
- Dynamic Steiner Tree Problem
- A General Approximation Technique for Constrained Forest Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximation Algorithms for Directed Steiner Problems
- Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
- Approximating Steiner Networks with Node-Weights
- Online Node-Weighted Steiner Tree and Related Problems
This page was built for publication: Online Node-weighted Steiner Forest and Extensions via Disk Paintings
