Online Node-weighted Steiner Forest and Extensions via Disk Paintings
DOI10.1137/14098692XzbMATH Open1370.68335OpenAlexW2620451143MaRDI QIDQ5737814FDOQ5737814
Authors: Vahid Liaghat, Debmalya Panigrahi, Mohammad T. 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
Recommendations
- Online node-weighted Steiner tree and related problems
- An optimal algorithm for online prize-collecting node-weighted Steiner forest
- Online Directed Spanners and Steiner Forests.
- scientific article; zbMATH DE number 1559550
- Parameterized analysis of the online priority and node-weighted Steiner tree problems
- On-line Steiner trees in the Euclidean plane
- Online Steiner tree with deletions
- Non-greedy online Steiner trees on outerplanar graphs
- Non-greedy online Steiner trees on outerplanar graphs
- Node-weighted Steiner tree approximation in unit disk graphs
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Cites Work
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- The Design of Competitive Online Algorithms via a Primal—Dual Approach
- A General Approximation Technique for Constrained Forest Problems
- Approximation Algorithms for Directed Steiner Problems
- Lower bound of the Hadwiger number of graphs by their average degree
- Efficient recovery from power outage (extended abstract)
- Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
- Dynamic Steiner Tree Problem
- The online set cover problem
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Heuristics for the fixed cost median problem
- Title not available (Why is that?)
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- A general approach to online network optimization problems
- Approximating Steiner networks with node-weights
- Title not available (Why is that?)
- Online Node-Weighted Steiner Tree and Related Problems
- On-line generalized Steiner problem
- The point-to-point delivery and connection problems: Complexity and algorithms
- An \(O(\log n)\)-competitive algorithm for online constrained forest problems
- Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
- Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
Cited In (8)
- Parameterized analysis of the online priority and node-weighted Steiner tree problems
- Tight bounds for online weighted tree augmentation
- Online constrained forest and prize-collecting network design
- Online Buy-at-Bulk Network Design
- Online Spanners in Metric Spaces
- Spider Covering Algorithms for Network Design Problems
- Covering problems in edge- and node-weighted graphs
- Timing matters: online dynamics in broadcast games
This page was built for publication: Online Node-weighted Steiner Forest and Extensions via Disk Paintings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5737814)
