Online Node-weighted Steiner Forest and Extensions via Disk Paintings
DOI10.1137/14098692XzbMATH Open1370.68335OpenAlexW2620451143MaRDI QIDQ5737814FDOQ5737814
Debmalya Panigrahi, Mohammad T. Hajiaghayi, Vahid Liaghat
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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- 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
- 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(logn)-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
Recommendations
- Title not available (Why is that?) 👍 👎
- On-line Steiner trees in the Euclidean plane 👍 👎
- Node-weighted Steiner tree approximation in unit disk graphs 👍 👎
- Online Node-Weighted Steiner Tree and Related Problems 👍 👎
- Online Steiner Tree with Deletions 👍 👎
- Online Directed Spanners and Steiner Forests. 👍 👎
- An optimal algorithm for Online Prize-Collecting Node-Weighted Steiner Forest 👍 👎
- Parameterized analysis of the online priority and node-weighted Steiner tree problems 👍 👎
- Non-greedy online Steiner trees on outerplanar graphs 👍 👎
- Non-greedy Online Steiner Trees on Outerplanar Graphs 👍 👎
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)
