Parameterized analysis of the online priority and node-weighted Steiner tree problems

DOI10.1007/s00224-019-09922-2zbMath1430.68453OpenAlexW2937747829WikidataQ128046645 ScholiaQ128046645MaRDI QIDQ2322716

Spyros Angelopoulos

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-019-09922-2

zbMATH Keywords

competitive analysisonline algorithmsmulticastingSteiner tree problemsmodels of communication networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear bounds for on-line Steiner problems
• On-line Steiner trees in the Euclidean plane
• The Steiner problem with edge lengths 1 and 2
• On the approximability of the Steiner tree problem.
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• On-line generalized Steiner problem
• A survey of combinatorial optimization problems in multicast routing
• A general approach to online network optimization problems
• THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM
• A threshold of ln n for approximating set cover
• The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
• A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry
• On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems
• 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
• The Performance of greedy algorithms for the on-line steiner tree and related problems
• Approximation Algorithms for Directed Steiner Problems
• On the approximability of some network design problems
• Reducibility among Combinatorial Problems
• Non-approximability results for optimization problems on bounded degree instances
• Online Steiner Tree with Deletions
• Steiner Tree Approximation via Iterative Randomized Rounding
• Online Node-Weighted Steiner Tree and Related Problems
• The power of deferral
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings