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

DOI10.1007/S00224-019-09922-2MaRDI QIDQ2322716zbMATH OpenOpenAlexWikidataFDO

Authors 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 analysismodels of communication networksmulticastingonline algorithmsSteiner tree problems

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)

Recommendations

• Online Priority Steiner Tree Problems
• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
• Online node-weighted Steiner tree and related problems
• Near-optimal online algorithms for prize-collecting Steiner problems
• scientific article; zbMATH DE number 1559550

Cites work

• A general approach to online network optimization problems
• A General Approximation Technique for Constrained Forest Problems
• A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A survey of combinatorial optimization problems in multicast routing
• A threshold of ln n for approximating set cover
• Approximation Algorithms for Directed Steiner Problems
• Dynamic Steiner Tree Problem
• scientific article; zbMATH DE number 6381651 (Why is no real title available?)
• scientific article; zbMATH DE number 5764797 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1559550 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Linear bounds for on-line Steiner problems
• Non-approximability results for optimization problems on bounded degree instances
• On the approximability of some network design problems
• On the approximability of the Steiner tree problem.
• On the competitiveness of the online asymmetric and Euclidean Steiner tree problems
• On-line generalized Steiner problem
• On-line Steiner trees in the Euclidean plane
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Online node-weighted Steiner tree and related problems
• Online Steiner tree with deletions
• Reducibility among combinatorial problems
• Steiner tree approximation via iterative randomized rounding
• THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM
• The Performance of greedy algorithms for the on-line steiner tree and related problems
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The Steiner problem with edge lengths 1 and 2
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(4)

• Online Priority Steiner Tree Problems
• Online node-weighted Steiner tree and related problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights

This page was built for publication: Parameterized analysis of the online priority and node-weighted Steiner tree problems

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